226. When does a graph have an Euler circuit or Euler path, and how do you find one?
MediumGraph algorithms
Show model answer
Undirected: ignoring isolated vertices, the graph must be connected. An Euler circuit (uses every edge once and returns to the start) exists iff every vertex has even degree; an Euler path exists iff exactly zero or two vertices have odd degree, and a path must start at one odd vertex and end at the other. Directed: every vertex needs in-degree = out-degree for a circuit; for a path, one vertex has out − in = 1 (start), one has in − out = 1 (end), all others balanced, and the underlying graph must be connected.
Hierholzer's algorithm builds the tour in O(V + E): walk from the start consuming unused edges until stuck, pushing vertices on a stack; when a vertex has no unused edges, pop it to the output. The output reversed is the Euler path or circuit. Contrast with Hamiltonian paths (visit every vertex once), which are NP-complete.