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.
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$.
- Clearly, the order is $m$.
- 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.
- 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.
- 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.