1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Graph theory line graph proof

  1. Nov 2, 2009 #1
    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:

    [tex]\sum(di choose 2)[/tex] 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!!!
  2. jcsd
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted

Similar Discussions: Graph theory line graph proof
  1. Graph theory trail proof (Replies: 11)

  2. Graph Theory Proof (Replies: 3)

  3. Graph theory proof (Replies: 3)