Evenness of line graphs
Task number: 4181
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.
