Graphs with open Eulerian trails
Task number: 4176
Characterize all graphs that have (not necessarily closed) Eulerian trail.
Solution
If the graph has a closed Eulerian trail, then it is connected and has all vertices of even degree.
If the graph has an open Eulerian trail, then it is connected and has exactly two odd-degree vertices – in particular the first and last vertex of the trail, the others have an even degree.
Answer
A graph has a Eulerian trail if it is connected and has at most two odd-degree vertices.
