Line graph proof

mathgirlie · #1 $Old$ November 1st, 2009, 01:43 PM

Let G be a non-empty graph of order n whose vertices have degrees (d1, . . . , dn) Provethat the size of L(G) is:
SUM(d_i choose 2)

Alright, this is what I tried so far:

Let G be a nonempty graph of order n whose vertices have deg(d_1...d_n).
By theorem that means that the size of G= (1/2)SUM(d_i)

By definition of the line graph, that means that order of L(G)=size G, and therefore,

order of L(G)= (1/2)SUM(d_i)

This is where I get stuck, by definition of the line graph, two vertices of L(G) have an edge between them if they share an endpoint in G. I understand the concept, but I really don't know how to write it out in my proof. I see that the of a vertex (lets say v1) is equal to the number of verticies in L(G) and we choose two of those verticies to draw an edge between in L(G) so that means that the number of edges in L(G) for v1=(deg(v1) choose 2). What would be a more formal way of writing that out?

Any tips would be great!

gmatt · #2 $Old$ November 2nd, 2009, 03:12 PM

Quote:

Originally Posted by mathgirlie $View Post$

Let G be a non-empty graph of order n whose vertices have degrees (d1, . . . , dn) Provethat the size of L(G) is:
SUM(d_i choose 2)

Alright, this is what I tried so far:

Let G be a nonempty graph of order n whose vertices have deg(d_1...d_n).
By theorem that means that the size of G= (1/2)SUM(d_i)

By definition of the line graph, that means that order of L(G)=size G, and therefore,

order of L(G)= (1/2)SUM(d_i)

This is where I get stuck, by definition of the line graph, two vertices of L(G) have an edge between them if they share an endpoint in G. I understand the concept, but I really don't know how to write it out in my proof. I see that the of a vertex (lets say v1) is equal to the number of verticies in L(G) and we choose two of those verticies to draw an edge between in L(G) so that means that the number of edges in L(G) for v1=(deg(v1) choose 2). What would be a more formal way of writing that out?

Any tips would be great!

Define $E_ {v_i} = \{(v_i, u) \in E\}$ and define $E'$ the set of edges in $L(G)$ . Define $E'_{v_i} = \{ (e_1, e_2) \in E' : e_1 \in E_{v_i} \text{ or } e_2 \in E_{v_i}\}$ . You need to show that $E'_{v} \cap E'_{u} = \emptyset$ whenever $u \neq v$ with $u,v\in V$ . Then it follows that $\bigcup_i E'_{v_i} = E'$ (because the $E_{v_i}$ 's are equivalence classes) and all that remains to prove to show your result is that $\left| E'_{v_i} \right| = \binom {deg(v_i)}{2}$ .

My advice is never take anything from granted in math. If you're at a point where you think its obvious but you don't know quite how to prove it, it most likely is NOT obvious and there is a subtlety that you need to iron out. At that point its most likely your intuition and as my first year math prof always said, your intution is correct only about half the time.

mathgirlie · #3 $Old$ November 2nd, 2009, 07:49 PM

So are you saying that E_vi is the set of edges in the original graph?

gmatt · #4 $Old$ November 2nd, 2009, 09:22 PM

Here I'm using the notation that G=(V,E) and L(G)=(V',E') and the E_v_i's are subsets of E that have v_i as a terminating node, and the E'_v_i 's are special subsets of E'.

Basically, what I'm doing is parititioning the edges in the line graph L(G) into disjoint subsets E'_v_i where each subset is defined to be the set of edges IN the LINE GRAPH such that they share the common vertex v_i in the original graph. If two edges share more than one vertex v_i then they are necessarily the same edge (because this is an undirected graph.) Once you have partitioned it into disjoint sets you just have to show that the size of each one of these sets is binom(deg(v_i), 2).