# Homework Help: [Graph theory] Formula for the size of a line graph

1. Apr 5, 2010

### dbh2ppa

1. The problem statement, all variables and given/known data
Let G be a graph of order n and size m.
V(G)={v1,v2,...,vn} and deg(vi)=ri.
Find a formula for the size of the line graph L(G) in terms of n, m, and ri.

2. Relevant equations
The http://en.wikipedia.org/wiki/Line_graph" [Broken] L(G) is the graph such that every vertex in L(G) corresponds to an edge in G, and two vertices in L(G) are adjacent iff the corresponding edges in G share a vertex.

3. The attempt at a solution
I know that the degree of any w in V(L(G)), when w is equivalent to some edge (va,vb) in G, is (ra-1)+(rb-1), that is to say ra+rb-2.
The size of L(G) would be (with it's vertices labeled from 1 to m).
$$\frac{\sum_{i=1}^{m} r_{a_{i}}+r_{b_{i}}-2}{2}$$
Where vai and vbi are the vertices of the edge in G corresponding to wi in L(G). This, however, seems to be the least elegant solution possible. Is there a better solution? Are there any errors in the one I wrote? (I really am not sure about it).

Last edited by a moderator: May 4, 2017