dancergirlie
Nov2-09, 04:20 PM
1. The problem statement, all variables and given/known data
Let G be a non-empty graph of order n whose vertices have degrees d1, . . . , dn.
The line graph of G is defined as follows: the vertices of L(G) are the edges of G, and two vertices of L(G) are adjacent if they share an endpoint in G. Prove that the size of L(G) is:
\sum(di choose 2) from i=1 to n
Hint: The size of Kd is (d choose 2)
2. Relevant equations
3. The attempt at a solution
Well I know that the SUM(deg v)=2|E|
meaning that |E| or the size of G is (1/2)SUM(di)
Which would mean that the order of L(G) would be (1/2)SUM(di)
I think that the line graph is a complete graph would would mean that would mean that the degree of each vertex would be (n-1), and in the case of the line graph would be ((1/2)SUM(di))-1
I don't really know if I'm on the right track, any help would be greatly appreciated!!!
Let G be a non-empty graph of order n whose vertices have degrees d1, . . . , dn.
The line graph of G is defined as follows: the vertices of L(G) are the edges of G, and two vertices of L(G) are adjacent if they share an endpoint in G. Prove that the size of L(G) is:
\sum(di choose 2) from i=1 to n
Hint: The size of Kd is (d choose 2)
2. Relevant equations
3. The attempt at a solution
Well I know that the SUM(deg v)=2|E|
meaning that |E| or the size of G is (1/2)SUM(di)
Which would mean that the order of L(G) would be (1/2)SUM(di)
I think that the line graph is a complete graph would would mean that would mean that the degree of each vertex would be (n-1), and in the case of the line graph would be ((1/2)SUM(di))-1
I don't really know if I'm on the right track, any help would be greatly appreciated!!!