$L(G)$ is an undirected graph without parallel edges and loops such that:

1. every edge in $G$ is an vertex in $L(G)$
2. two vertices in $L(G)$ are connected by edge only if their edges in $G$ have a common vertex.

The mission is to express the number of edges in $L(G)$ as a function of the vertices' degrees in $G$.

I have the solution, but I don't understand one thing in it.

Let's look at a vertex $v$ in $G$. Every pair of edges connected to $v$ gives an edge to $L(G)$. I don't understand why $\binom{d(v)}2$ is the number of edges which $v$ creates; why it isn't $\frac{d\left(v\right)}{2}$, if every two edges connected to $v$ add an edge?

Can some one explain it to me, maybe by drawing an example, if it needed, because I tried and still don't see it.

  • 1
    $\begingroup$ I just wrote it as it is written in my book, I agree that it should be written clearly, but it isn't mentioned as we expect it to be. So that's how it is formulated, I guess the meaning is as you said. $\endgroup$ – Ilya.K. Mar 4 '16 at 11:59
  • $\begingroup$ Yes, you write, it's a typo 100%, fixed it at the post. $\endgroup$ – Ilya.K. Mar 4 '16 at 12:00

Suppose that $G$ is the following graph:

                        / \  
                       c   d

It has edges $ab,bc$, and $bd$, so $L(G)$ has three vertices for which I will use the labels $v_{ab},v_{bc}$, and $v_{bd}$.. The edges $ab$ and $bc$ have a vertex in common, so the vertices $v_{ab}$ and $v_{bc}$ are connected by an edge in $L(G)$. In fact, each of the three pairs of edges of $G$ have vertex $b$ in common, so the corresponding vertices in $L(G)$ are connected by edges. Thus, $L(G)$ looks like this:

                       /  \  
                     1/    \2  
                     /      \  

(Here I’ve written v_ab instead of $v_{ab}$, since I can’t write true subscripts in preformatted code.

Now let’s compare this with the argument in question. Specifically, we’ll look at vertex $b$ of $G$. Every pair of edges incident at $b$ create an edge in $L(G)$. Those pairs of edges are the pairs $\{ab,bc\}$, $\{ab,bd\}$, and $\{bc,bd\}$. the first of these pairs created the edge labelled $1$ in $L(G)$; the second, the edge labelled $2$; and the third, the edge labelled $3$.

The number of pairs of elements of an $n$-element set is $\binom{n}2=\frac{n(n-1)}2$; in this case $n=d(b)=3$, so we have


pairs of edges incident at vertex $b$. Note that we could not possibly get $\frac{d(b)}2=\frac32$ edges of $L(G)$ from the vertex $b$: that isn’t even an integer.


You get $\binom{d(v)}2$ since you need to calculate the number of possible, unordered, pairs when you have $d(v)$ elements. Note especially that, if we call one of the edges in $v$ by the name $a$ then $a$ has $d(v)-1$ different other edges to be paired together with. Thus the answer $d(v)/2$ far from the truth.

  • $\begingroup$ Wait a second, all I see from the given data, that the number of vertices in L(G) will be as the number of edges in G. And the edges of L(G) seemed to be determinated by the second condition, I don't see why I have a level of freedom in possibilities. $\endgroup$ – Ilya.K. Mar 4 '16 at 12:08

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.