# When the line graph of a line graph gives us the original graph?

Definition:

Let $G$ be a graph, the line graph of $G$ denoted of $L(G)$ is defined as follows:

-The vertices of $L(G)$ are the edges of $G$

-Two vertices of $L(G)$ are adjacent iff their corresponding edges in $G$ are incident G.

Question?

Let $G$ be $d$-regular graph. For $d=2$, $G$ will be cycle graph, in this case it is easy to check that $L(G)=G$, thus $L(L(G))=G$ ($i.e.$ line graph of the line graph gives us the initial graph).

My question is for which $d\geq 3$ we have $L(L(G))=G$?

I think that $L(L(G))=G$ if and only if $d=2$, but I'm not sure how to prove it.

Any idea will be useful!

• +1 for question and answer, I think I can use this result as check for my linear algebra implementation of the mapping $L(G)$... – draks ... Apr 5 '16 at 8:46

Let $G$ be $k$-regular graph (that is $d(G)=k$), then $L(L(G))=G$ if and only if $k=2$
-If $k=2$, then $L(L(G))=G$.
-If $L(L(G))=G$, then $$d(L(L(G)))=d(G)=k$$
But we know that $d(L(G))=2k-2\Rightarrow d(L(L(G)))=4k-6$, then $$4k-6=k\Rightarrow k=2$$