# Size and Order of a Line Graph of Another Graph G

This is an extension of the problem at this thread: Graphs, line graph and complement of graph.

Just to reiterate definitions:

The line graph $L(G)$ of a graph $G$ is defined in the following way: the vertices of $L(G)$ are the edges of $G$, $V(L(G))=E(G)$, and two vertices in $L(G)$ are adjacent if and only if the corresponding edges in $G$ share a vertex.

Question:

Suppose $G$ has $n$ vertices, labeled $v_1,v_2,\ldots,v_n$ and the degree of vertex $v_i$ is $r_i$. Let $m$ denote the size of $G$, so $r_1+r_2+\ldots+r_n=2m$. Find formulas for the order and size of $L(G)$ in terms of $n,m,$ and $r_i$.

So far:

1. Clearly, the order is $m$.
2. Suppose that the edge $e=(v_i,v_j)$ exists in $G$. Then, the $\deg(e)=r_i+r_j - 2$ in $L(G)$, because at the $v_i$ end, $e$ shares $v_i$ with $r_i - 1$ other edges, and at the $v_j$ end, $e$ shares $v_j$ with $r_j - 1$ other edges.
3. I tried to use the above to sum over all the edges in $G$, but this depends on knowing which edges exist in the graph $G$, which we are not given. We only know the degree sequence, not the edges.
4. Another approach I tried was to find this expression for a regular graph with degree $k$, and this can be found using the above: $$m(2k - 2) = 2|E(L(G))| \implies |E(L(G))| = m(k - 1).$$ I then tried this for a complete graph (so $k = m - 1$), and then removing edges one at a time until it becomes $G$, but this also requires knowledge of the edges.

Any help would be greatly appreciated. One piece of information that I seem to be not using is the variable $n$, the order of $G$, but I am not sure where it would be appropriate to use.

• Assuming your graphs don't have multiple edges, each vertex of degree $r$ in $G$ contributes $r(r-1)/2$ edges to the line graph. May 23, 2013 at 19:37
• Wow, that is neat! Instead of enumerating by the edges of $G$ as I did, you enumerate by the vertices of $G$ and their effect on the size of $L(G)$. And yours is true because for each vertex $v$ with $\deg(v)=r$ in $G$, all pairs of edges share the $v$, so consequently, this adds $\binom{n}{2}$ edges in $L(G)$. Beautiful and simple, thank you. Do you want to make that an answer so I can accept it? May 23, 2013 at 21:59

The way I found it easiest to think about is that every vertex in G of degree r corresponds to r vertices that are connected among each other in L(G), so every vertex corresponds to a complete graph of order r. Then it corresponds to r(r-1)/2 edges (the number of edges in a complete graph). Then you just sum over $$\frac{r^2-r}{2}$$ to get the size of L(G) (from Wolfram Mathworld): $$\ \frac{1}{2}\sum_{i=1}^n (r_i)^2 - m$$