Given degree sequence of Graph G, find the number of edges in its line graph

1k Views Asked by At

Let the degree sequence of a graph G be $d_1, d_2, ....d_V$. In Line graph of G L(G), edge of G becomes vertex of L(G). If the incident vertices on an edge of G has degree $d_i, d_j$ then corresponding edge which is vertex in L(G) has degree $d_i-1+d_j-1=d_i+d_j-2$.

So degree sequence of L(G) $:= d_1+d_2-2, d_2+d_3-2, ......d_{v-1}+d_v-2$

Number of edges of L(G) = half the degree sum = $\frac {1}{2}\{d_1+d_v+2(d_2+d_3+d_4+...d_{v-1})-2(v-1) \}=\frac {1}{2}\{2(2E)-d_1-d_v-2v+2\},$ where E is number of edges of G.

How to proceed now? Please have a look.

1

There are 1 best solutions below

4
On BEST ANSWER

While your idea of using the "sum of the degrees is twice the edges" formula is a good one, you need to be a bit more careful with how you add things up. Let's work through an example with the below graph

Graph

Here there's five lines, which I'll denote by $\ell_{12}, \ell_{14},$ and so on. The sum of the degrees is \begin{eqnarray*} & & \deg(\ell_{12})+\deg(\ell_{14})+\deg(\ell_{23})+\deg(\ell_{24})+\deg(\ell_{34}) \\ &=& (d_1+d_2-2)+(d_1+d_4-2)+(d_2+d_3-2)+(d_2+d_4-2)+(d_3+d_4-2) \\ &=& 2d_1 + 3d_2 + 2 d_3 + 3d_4 - 10 \end{eqnarray*}


One key thing to notice here is that we're adding up not just $(d_1+d_2-2)$, $(d_2+d_3-2)$, etc. Instead, we're adding up the degrees for every single edge in the graph. This means that some vertex degrees are being added many times. In fact, for any vertex $v_i$, we're including its degree as part of the sum of $d_i$ different edges. In the above example, vertex $2$ had degree $3$, so when we added up all the edge degrees we included $d_2$ a total of $3$ times. More generally, when we add up the edge degrees, we're including $d_i$ (the degree of vertex $i$) a total of $d_i$ different times.

So the analogue of "$2d_1+3d_2+2d_3+3d_4$" is $$d_1(d_1)+d_2 (d_2) +d_3 (d_3) +\dots+d_v (d_v) = d_1^2+d_2^2+\dots+d_v^2.$$

The $-10$ part corresponds to subtracting off a $2$ for each edge in the graph. So more generally we'd be subtracting off $2|E|$. This means that we have

\begin{eqnarray*} 2 (\# \textrm{ edges in } E(G)) &=& \sum_{(i,j) \in E(G)} \deg(\ell_{ij}) \\ &=& \sum_{i=1}^v d_i^2 - 2|E| \\ &=& \sum_{i=1}^v d_i^2 - d_i \end{eqnarray*} Where for the last step I used that the number of edges was half the sum of the vertex degrees.