(adsbygoogle = window.adsbygoogle || []).push({}); 1. The problem statement, all variables and given/known data

Let G be a graph of order n and size m.

V(G)={v_{1},v_{2},...,v_{n}} and deg(v_{i})=r_{i}.

Find a formula for the size of the line graph L(G) in terms of n, m, and r_{i}.

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 (v_{a},v_{b}) in G, is (r_{a}-1)+(r_{b}-1), that is to say r_{a}+r_{b}-2.

The size of L(G) would be (with it's vertices labeled from 1 to m).

[tex]

\frac{\sum_{i=1}^{m} r_{a_{i}}+r_{b_{i}}-2}{2}

[/tex]

Where v_{ai}and v_{bi}are the vertices of the edge in G corresponding to w_{i}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).

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

Can you offer guidance or do you also need help?

**Physics Forums | Science Articles, Homework Help, Discussion**