Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have a hard time trying to understand this prove.

Find an expression for the number of edges of $L(G)$ in terms of the degrees of the vertices of $G$.

Let $\{v_1, v_2, . . . , v_n\}$ be the vertices of $G$ and let $d_i$ be the degree of the vertex $v_i$. An edge ${v_i, v_j}$ will be adjacent to $d_i − 1 + d_j − 1$ edges. Until this point I understand it. Since there are $d_i$ edges that contain $v_i$ in $G$, the sum of the degrees of the vertices in $L(G)$ will be $\sum_{i=1}^n d_i(d_i − 1)$ and so the number of edges in $L(G)$ is $\sum_{i=1}^n \frac{d_i(d_i − 1)}{2}$.


share|cite|improve this question
up vote 3 down vote accepted

I think the given proof is a bit confusing.

Try this one:

An edge in $L(G)$ is a $2$-set $\{e_1,e_2\}$ of edges in $G$ with which are adjacent to a common vertex $v$. This vertex $v$ is uniquely determined by $\{e_1,e_2\}$. If a vertex $v$ has degree $d$, there are $\binom{d}{2}$ $2$-sets $\{e_1,e_2\}$ such that $e_1$ and $e_2$ are adjacent to $v$.

So the total number of edges in $L(G)$ is $$ \sum_{i = 1}^n \binom{d_i}{2} = \sum_{i = 1}^n \frac{d_i(d_i-1)}{2}\text{.} $$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.