Eulerian path: use every edge exactly once
Choose and undo roads on a four-vertex map, distinguish edge coverage from visiting every vertex, and see how a stack builds an Eulerian path.
An Eulerian path uses every edge exactly once and may revisit vertices. For an undirected graph with edges, it exists when all vertices with edges are connected and either zero or two vertices have an odd number of incident edges.
Four roads connect A–B, B–C, C–A and C–D. The walk D → C → A → B → C uses every road once. It visits C twice, which is allowed: the roads, not the towns, must each be used once.
The road to D must be covered as well as the triangle between A, B and C. That is what makes the starting point matter. Reaching all four towns is not enough, and choosing an attractive route around the triangle can leave the last road unused.
What the route must cover#
In this illustrative, undirected graph, D → C → A → B → C covers all four roads. The reverse route works too. Repeating C is necessary here because three roads meet there.
Compare that with A → B → C → D. It visits each town once, making it a Hamiltonian path, but it leaves A–C unused. The same map makes the distinction visible: one problem counts used roads; the other counts visited towns.
Predict whether that route covers every edge, then choose A, B, C and D. All vertices have been visited, yet the edge A–C remains unused and D has no unused edge to leave by. Reset and choose D → C → A → B → C: the second visit to C is allowed because each step uses a different road.
Build a route that uses each edge once
Illustrative example on the triangle-with-tail graph: start at D, then choose C, A, B and C. Does returning to C break the once-only rule for edges?
Follow an unused edge on each move. Use every edge once; visiting a vertex more than once is allowed.
Changing the route requires JavaScript. The graph and worked example remain available without it.
Connections in this graph
- A: B, C
- B: A, C
- C: A, B, D
- D: C
- Current route
- Not started
- Visited vertices 0 / 4
- None
- Unvisited vertices
- A, B, C, D
- Used edges 0 / 4
- None
- Unused edges
- A–B, A–C, B–C, C–D
- Available next vertices
- A, B, C, D
Choose a starting vertex. The route must use all 4 edges once; it may revisit vertices.
Triangle-with-tail example and failed choice
D → C → A → B → C uses all four edges once and visits C twice. A → B → C → D visits every vertex once, but leaves A–C unused, so it is not an Eulerian path.
After D → C, choosing D again would reuse the same undirected edge C–D. Reversing direction does not make it a new edge.
This workbench checks your chosen route on two small, simple undirected graphs. It does not search all routes, minimise travel cost, or model directed edges, parallel edges or self-loops. Getting stuck describes this route, not every possible route.
Undo removes the last step and makes its road available again. It does not let a finished route use the same road twice. The workbench checks your choices on two small, simple undirected maps; it does not implement the stack algorithm below or minimise distance. Its maps have no weights, parallel edges or self-loops.
A vertex is a town in this example, and an edge is a road. A vertex’s degree is the number of edges meeting it. A and B each have degree 2, C has degree 3, and D has degree 1.
Why the endpoints matter#
At an intermediate town, each arrival needs a departure along another unused road. Those roads are used in pairs. Only the start can have a departure without an arrival, and only the end can have an arrival without a departure.
That gives the test for an undirected graph whose vertices with edges are connected:
| Number of odd-degree vertices | What is possible |
|---|---|
| Zero | A route that returns to its start: an Eulerian circuit. |
| Two | An open route starting at one odd-degree vertex and ending at the other. |
| More than two | No route using every edge exactly once. |
C and D are the two odd-degree vertices in the example. Starting at A cannot work: it would leave more unmatched arrivals or departures than a single route can have.
Degree counts alone are not enough. Two disconnected triangles have no odd-degree vertices, but a single walk cannot jump from one triangle to the other. Ignore isolated vertices, which have no edges to cover. For a self-loop, count both ends of the edge at its vertex. Directed graphs need different conditions involving incoming and outgoing edges.
Change the workbench to its star map. The centre A has degree 3; B, C and D each have degree 1. All four are odd, so no starting point can cover every edge in one walk. This degree argument establishes that no Eulerian path exists; getting stuck after a particular choice would not be enough by itself.
Build the route without losing a branch#
Hierholzer’s algorithm constructs the route using a stack: a list where the last added vertex is the next one examined. Follow unused edges and push their destinations. When the top vertex has no unused edges left, remove it from the stack and add it to an output list. Reverse that output at the end.
To see why the reversal matters, deliberately take the awkward first step C → D:
| Action | Stack | Output collected so far |
|---|---|---|
| Start at C | C |
empty |
| Take the unused road to D | C, D |
empty |
| D has no unused road; remove it | C |
D |
| Follow the unused triangle edges | C, A, B, C |
D |
| Remove the remaining vertices, last first | empty | D, C, B, A, C |
Reverse the output to obtain C → A → B → C → D. The early dead end at D becomes the end of the finished route rather than stranding the triangle. The stack versus queue guide explains the last-in, first-out behaviour used here.
With an adjacency structure that consumes each edge efficiently, construction and the associated graph checks take O(V+E) work for V vertices and E edges. In an undirected implementation, mark an edge once for both directions; two adjacency entries do not represent two separate roads.
Before constructing a route, check connectivity and the allowed endpoints. Afterwards, check that it contains exactly E edge traversals. None of this minimises travel cost between two places; Dijkstra’s algorithm answers that different question.
Questions people also ask
2 QUESTIONSCan an Eulerian path revisit a vertex?
Yes. The once-only rule applies to edges. A Hamiltonian path instead visits each vertex once and may leave edges unused.
What about isolated vertices or an empty graph?
A vertex with no edges does not prevent a route covering the graph’s edges. The tests here assume at least one edge. For an edgeless graph, an implementation must choose how to represent the trivial empty-edge walk.