Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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}$.

From: http://garsia.math.yorku.ca/~zabrocki/math3260w03/hw1sln.pdf

share|improve this question
add comment

1 Answer

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|improve this answer
add comment

Your Answer

 
discard

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.