8
$\begingroup$

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

$\endgroup$
11
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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