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.

Difficulty level: Easy task (using definitions and simple reasoning)
Proving or derivation task
Cs translation
Send comment on task by email