## Evenness of line graphs

Show that if a graph $$G$$ is Eulerian, then its line graph is also Eulerian.

Does the reverse implication also apply?

The vertices of the line graph $$L(G)$$ are the edges of $$G$$. Two vertices in $$L(G)$$ representing the edges $$e$$ and $$f$$ are adjacent if and only if $$e$$ and $$f$$ have a common vertex.

• #### Solution

The connectivity is preserved in the line graph, because if there is a path (as a sequence of vertices) between any vertices of the $$G$$, it is possible for the prescribed edges $$e$$ and $$f$$ find the path from one end vertex $$e$$ to one of the end vertices $$f$$.

This path, viewed as a sequence of edges in $$G$$, is a path viewed as a sequence of vertices in $$L (G)$$.

If we count the edges sharing at least one vertex with an edge $$e = (u, v)$$ in $$G$$, then we get $$deg_{L (G)} (e) = deg_G (u) + \ deg_G (v) -2$$ which is an even number assuming that $$G$$ is Eulerian.

The reverse implication does not apply, e.g. the linegraph $$L (K_4)$$ is four-regular and therefore also Eulerian, while $$K_4$$ is not Eulerian.  