How Do You Calculate the Size of a Line Graph in Graph Theory?

[dancergirlie]

Homework Statement

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)

Homework Equations

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!

 

[mighty2000]

Thank you for your question. Your approach is definitely on the right track. You have correctly identified that the size of G, |E|, is equal to (1/2)SUM(di). This means that the average degree of the vertices in G is (1/2)SUM(di)/n.

Now, to prove the size of L(G), we need to consider the number of edges in L(G). Since the vertices of L(G) are the edges of G, there are n edges in L(G). We can also see that each edge in L(G) corresponds to a pair of vertices in G that share an endpoint. This means that for each edge in L(G), there are two vertices in G that share an endpoint. Therefore, the degree of each vertex in L(G) is equal to the number of edges in G that share that vertex as an endpoint.

Using the hint given in the question, we can see that the size of Kd, a complete graph with d vertices, is (d choose 2). This means that the degree of each vertex in L(G) is (di choose 2), where di is the degree of the corresponding vertex in G. Therefore, the total number of edges in L(G) is the sum of the degrees of all vertices in L(G), which is equal to:

\sum(di choose 2) from i=1 to n.

I hope this helps clarify the solution for you. Let me know if you have any further questions. Keep up the good work!