Finds path visiting every edge exactly once in undirected graphs
Time: O(V + E)
Space: O(V)
Use Case: Route planning, puzzle solving, circuit design
Algorithm Execution
Select an algorithm and generate steps to begin visualization
About Eulerian Path (Undirected)
An Eulerian path traverses every edge of a graph exactly once; an Eulerian circuit does so and returns to its start. Leonhard Euler founded graph theory in 1736 by proving the Seven Bridges of Konigsberg admits no such walk.
How it works
Existence is easy to check: a connected undirected graph has an Eulerian circuit exactly when every vertex has even degree, and an Eulerian path when exactly zero or two vertices have odd degree. Hierholzer's algorithm constructs the walk in O(E) time: follow unused edges until returning to the start, then repeatedly splice in detour cycles from vertices that still have unused edges.
Applications
Eulerian paths solve route inspection problems such as snow plowing, street sweeping and postal delivery, reconstruct DNA sequences from k-mers in bioinformatics, and generate De Bruijn sequences. The parity-based existence test is a classic interview question distinguishing it from the much harder Hamiltonian problem.