A delivery route may need to traverse every street, while revisiting intersections is allowed. This is an edge problem, not the vertex problem of finding a Hamiltonian cycle. We work with finite undirected graphs without loops or parallel edges.
Definition 2.1.1
(Trails and Eulerian circuits)
A trail is a walk that does not repeat an edge. An Eulerian circuit is a closed trail containing every edge exactly once.
For a graph with no edges, the length-zero walk at a vertex is a circuit under our convention; the empty vertex set is excluded.
Theorem/proposition
Theorem 2.1.2
(Even-degree criterion for an Eulerian circuit)
A finite graph with at least one edge has an Eulerian circuit if and only if all vertices of positive degree belong to one connected component and every vertex has even degree. Isolated vertices do not affect the route.
Proof
(Pairing arrivals and departures)
The circuit joins all endpoints of edges. At each visit to a vertex, the route uses a distinct arrival edge and departure edge; for the initial vertex pair the final arrival with the initial departure. Thus its incident edges are partitioned into pairs and its degree is even.
Proof
(Closing and splicing unused-edge trails)
Begin at a positive-degree vertex and follow unused edges until none is available. The trail must end where it began. Indeed, at any other vertex, the used incident edges consist of pairs for completed visits plus one arrival; its even degree guarantees an unused departure. If all edges have been used, we are done. Otherwise connectedness of the positive-degree vertices gives a vertex on the current closed trail incident to an unused edge: follow a path from the trail to an unused edge and take the first unused edge on the path. The unused subgraph has even degrees, since deleting the edges of a closed trail removes an even number at each vertex. Start another unused-edge trail there, which also closes, and splice it into the original trail. Each splice uses at least one additional edge. Finiteness guarantees termination with all edges used.
Common mistake
(Connectivity is needed only among positive-degree vertices)
Connectivity of the whole graph is unnecessarily strong: a triangle plus an isolated vertex has a circuit through every edge. On the other hand, two disjoint triangles have all degrees even but no single trail can cover both components. Both hypotheses have a role.
Worked examples
Worked example 2.1.3
(Two triangles sharing one vertex)
Let two triangles and share only vertex . Their degrees are , so an Eulerian circuit exists: . The repeated vertex is allowed; no edge is repeated. This route is not a Hamiltonian cycle because occurs twice before closure.
Exercises
Quick check
(Can a connected graph have exactly one odd-degree vertex?)
Solution · Answer
No. The sum of all degrees is , since every edge has two ends. A sum is even only when it contains an even number of odd summands.
Quick check
(Show that a connected graph with exactly two odd-degree vertices has a trail using every edge exactly once, starting at and ending at .)
Solution · Answer
Add a new auxiliary vertex and edges . All degrees in the enlarged graph are even and its positive-degree vertices are connected, so it has an Eulerian circuit. Rotate that circuit so that it starts at , then remove its first and last edges, the only edges incident to . The remaining trail uses each original edge once and goes between and ; reverse it if necessary to start at . The auxiliary construction avoids assuming that was absent.
Open trails and the odd-degree condition
Theorem 2.1.4
(Two-odd-vertex criterion for an open trail)
The circuit theorem gives a complete criterion for open Eulerian trails too. Suppose the graph has at least one edge and all its positive-degree vertices lie in one component. It has a trail using every edge exactly once with distinct endpoints if and only if exactly two vertices have odd degree. Those vertices are its endpoints.
Proof
(Unpaired edges at the two ends)
For necessity, pair arrival and departure edges at each internal visit. At the starting vertex one departure is unpaired, and at the ending vertex one arrival is unpaired. All other incident edges pair, so the two endpoints are odd and every other vertex is even. The argument works even when the trail revisits an endpoint before the end: those intermediate visits still contribute pairs. Sufficiency was established in the exercise on trails between two odd-degree vertices by adding a new auxiliary vertex and deleting its two incident edges from a circuit. Using a new vertex avoids introducing a parallel edge if the two odd vertices were already adjacent.
In a graph with no odd-degree vertices, a trail that uses every edge and begins at a positive-degree vertex must end where it began. A graph with four odd-degree vertices cannot have one trail using all edges, though it might admit several trails whose union contains them. The statement also needs connectivity among positive-degree vertices: two disconnected edges have four odd vertices, while two disconnected triangles have zero, yet neither has a single route through all edges.
Worked example 2.1.5
(A pendant edge creates two odd vertices)
Add a pendant edge to the two triangles and . Degrees of and become 5 and 1; all other degrees remain 2. An open Eulerian trail is . It starts and ends at the two odd vertices. Starting at is impossible for a trail covering all edges, because its endpoints must be and .
From proof to an algorithm
Cycle splicing proves existence, but repeatedly searching the entire route for a splice point can waste time. A stack records vertex occurrences still being processed. It allows insertion implicitly: finish an unused-edge excursion before returning to an earlier occurrence. Repeated occurrences of the same vertex are separate stack entries.
Assume first that there is at least one edge, all positive-degree vertices lie in one component, and all degrees are even. Choose a positive-degree start . Give the edges distinct identifiers. In the adjacency list at each endpoint, store the other endpoint and that same identifier. A single Boolean flag used[e] belongs to the edge, not separately to either endpoint. Each vertex has a cursor into its adjacency list, initially at the first entry.
The stack procedure
Initialize a stack containing only , and an empty output list . While the stack is nonempty, let be its top vertex.
- Advance the cursor at past entries whose edge is already marked used.
- If an entry remains, advance the cursor past it, mark used, and push a new occurrence of onto the stack.
- Otherwise pop the top occurrence of and append to .
When the stack is empty, reverse to obtain the route. Each pushed occurrence can also remember the edge by which it was entered. Listing these identifiers as their occurrences are popped, omitting the initial occurrence's empty identifier, and reversing that list supplies the corresponding edge order.
The cursor must not be reset on a later visit. Nor does popping make any edge unused again. A stack is last-in, first-out: after a pop, the algorithm resumes at the preceding occurrence, possibly of a vertex already seen many times.
Theorem 2.1.6
(The stack procedure returns an Eulerian circuit)
Under the stated connectivity and even-degree hypotheses, the reversed output is a closed trail starting at that uses each of the edges exactly once. It contains vertex occurrences.
Why popping produces the right order
Proof
(Phases return to their start)
Group consecutive pushes into phases: a phase starts at the current top and ends just before the next pop. Initially the unused graph has even degrees. If a phase starts at and cannot continue at , its used edges give odd used degree at , whereas the degree there was even before the phase. Some unused edge at would remain, a contradiction. Thus every nonempty phase returns to its starting vertex. A phase with no push simply stays there. Removing a closed trail changes every degree by an even number, so after a whole phase the unused graph again has even degrees. This induction concerns completed phases; degrees need not stay even during an individual push.
The first popped vertex is therefore . Consider any later pop. Immediately after the previous vertex occurrence was popped, its predecessor became the stack top, unless the stack was empty. The stack edge entering that occurrence of joins to . Any intervening push phase starts and ends at , so the next popped vertex is . Consequently consecutive entries in are adjacent, with their joining edge exactly the entering edge of the earlier popped occurrence. Each pushed occurrence has one distinct entering edge, and every such occurrence is popped once. Thus , and hence its reversal, uses every selected edge exactly once. The initial bottom occurrence has no entering edge; it is popped last, giving last entry . So the returned route starts and ends at .
No edge is left unselected. Every vertex ever reached is eventually popped with no unused incident edge. If an unused edge remained in the positive-degree component, take a path from to an endpoint of it. If the entire path was selected, that endpoint was reached. Otherwise the first unselected path edge has a reached preceding endpoint. Either case contradicts exhaustion at a reached vertex. There are therefore pushes beyond the initial occurrence and pops.
Proof X-ray
Popping is an insertion rule, not a second traversal
The algorithm does not physically walk backwards along a used edge when it pops. It records the finished order of occurrences. A closed excursion explored at is inserted at that occurrence when the output is reversed. Marking edges prevents reuse; residual parity ensures the reverse-pop list joins up. These are different parts of the proof.
Worked example 2.1.7
(Tracing the two shared triangles)
Take edges , start at , and choose the first triangle before the second. The stack first becomes . The last has no unused edge, so it is popped and ; the stack is . Now still has unused edges, so push along , giving stack . Its top is exhausted and is popped. Continuing to pop gives
Reversal gives , exactly the circuit obtained by inserting into . The temporary output was not a declaration that all edges were covered. The earlier occurrence of was still waiting on the stack.
Running time and open trails
In the adjacency-list model, there are entries. Each cursor moves only forwards, so at most entries are passed in total, including entries whose edge was selected from its other endpoint. Each edge causes one push, and each occurrence one pop and append. Reversal takes operations. Degree counting and a preliminary search among positive-degree vertices take time, so the full procedure takes time and space, assuming constant-time indexed vertex/edge access. The bound includes isolated vertices in . If each vertex instead has a forward cursor through its adjacency-matrix row, at most cells are inspected, giving an implementation. Restarting a row scan on each visit can cost more; the representation and cursor rule both matter.
For an open trail with odd endpoints , use the previously proved auxiliary construction: add a new vertex and edges , run the circuit algorithm starting at , and delete the first and last edges. Vertex has degree two, so it occurs only at the start and finish of this circuit. The remainder is an original-edge trail between and ; reverse it if its orientation is unwanted. Adding one vertex and two edges preserves the linear bound. An edgeless graph with a vertex is handled separately by returning that vertex alone.
Practice: checking an implementation
Quick check
(An implementation runs from one triangle in the disjoint union of two triangles. Its returned sequence is a valid closed trail. Why must it still be rejected as an Eulerian circuit of the whole graph?)
Solution · Answer
Only three of the six edges are selected, giving four instead of seven vertex occurrences. The other component is unreachable. A certificate must cover the given whole edge set, not merely give a closed trail. The preliminary positive-degree connectivity check would already reject this input.
Quick check
(Omit the parity check and run from leaf in the three-edge star with center and other leaves . Select , then , then, after popping , select . What does the reversed output show?)
Solution · Answer
The pop list is , whose reversal is . Although all three edge flags are set and the list has occurrences, is not an edge. Four odd-degree vertices violate both Eulerian criteria. Thus edge-count and flag checks alone do not prove correctness of the returned vertex sequence; check consecutive endpoints and the claimed edge identifiers too. The theorem's parity hypothesis is what guaranteed closed push phases.
Eulerian is not Hamiltonian
Concept lensCombinatorial
Edges and vertices answer different questions
An Eulerian circuit uses every edge once; a Hamiltonian cycle visits every vertex exactly once before returning to its starting point. These are distinct requirements. The two triangles sharing one vertex are Eulerian, as above, but have no Hamiltonian cycle: removing their shared vertex disconnects the graph, whereas deleting any one vertex from a Hamiltonian cycle leaves a path through all the others. Thus a graph containing such a cycle must remain connected after any vertex is removed. This condition is necessary, not sufficient in general.
Conversely, the complete graph on four vertices has a Hamiltonian cycle , but every vertex has degree 3, so it has no Eulerian circuit. It has six edges; the displayed Hamiltonian cycle uses only four of them. A closed walk that visits every vertex is also not automatically Hamiltonian, since it may repeat vertices.
Quick check
(The graph is a square with diagonal . Find all possible endpoints of an open Eulerian trail and give one such trail.)
Solution · Answer
Degrees are , so the only possible endpoints are . One trail is . It uses the four square edges and the diagonal exactly once.
Quick check
(A graph consists of a triangle and a separate isolated vertex. Does it have an Eulerian circuit? Does it have a Hamiltonian cycle on all four vertices?)
Solution · Answer
The triangle itself is an Eulerian circuit because the isolated vertex has no incident edges to cover. There is no Hamiltonian cycle through all four vertices: the isolated vertex has no edge by which a cycle could enter or leave it. This comparison depends on the stated convention that isolated vertices do not obstruct an Eulerian circuit.
Common mistakes
Common mistake
(The first closed trail need not be complete)
The instruction to follow unused edges until no continuation exists builds a closed trail under the even-degree hypothesis, but that first trail need not include every edge. In the shared-triangle example, is already closed and has no unused edge incident to , although the other triangle is still unused. Stopping at that point would produce an incomplete answer. Splicing at is the step that connects the local trail to the remaining edges.
This also explains why connectivity is used twice in the reasoning. It is necessary for any single route to reach the endpoints of all edges. In the constructive proof, it additionally guarantees a place on the current trail from which some unused edge can be reached. Let be a vertex on the trail and choose a path from to an endpoint of an unused edge. If all edges on the path are already used, its endpoint is itself on the trail and is incident to an unused edge. Otherwise the first unused path edge has a preceding endpoint on the trail, because all earlier path edges occur in the trail. In either case a splice point exists.
Quick check
(A graph has a vertex of degree 5 and every other vertex has even degree. Is this possible?)
Solution · Answer
No. The degree sum would be odd, contradicting . This contradiction holds whether or not the graph is connected. It does not imply that every even number of odd-degree vertices is sufficient for an Eulerian trail: four odd vertices already rule out one trail.
Quick check
(In the shared-triangle graph, verify directly that is an Eulerian circuit.)
Solution · Answer
The consecutive edges are . They are all distinct and are precisely the six edges of the graph. The first and final vertices are both . The repeated occurrence of is permitted because the definition forbids repeated edges, not repeated vertices.
Summary
For a nonempty finite graph, discard isolated vertices when checking the connectivity condition. All remaining degrees even gives a closed Eulerian trail; exactly two odd degrees gives an open trail between those vertices. A trail with repeated vertices can still be Eulerian, but repeated edges violate the definition. The parity test proves existence, while an explicit list of edges supplies a checkable route. Hamiltonian cycles impose a different, vertex-based requirement.
These criteria apply to the finite undirected graphs specified above; directed graphs require separate in-degree and out-degree conditions.