Skip to interview prep
Apexed

226. When does a graph have an Euler circuit or Euler path, and how do you find one?

MediumGraph algorithms

Technical
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.

When does a graph have an Euler circuit or Euler path, and how do you find one — Data structures & algorithms interview question — Apexed