A walk may revisit a vertex without repeating an edge
Suppose we must inspect every road segment exactly once. Returning to an intersection is allowed; traversing the same segment twice is not. The distinction between vertices and edges is essential: an Euler circuit can revisit a vertex many times, unlike a cycle in the usual simple-graph sense.
Throughout, is a finite undirected multigraph with at least one vertex. Parallel edges are distinct edges; loops are allowed and contribute two to the degree of their vertex.
Definition 2.2.1
(Trails, Euler trails and Euler circuits)
A trail is a walk that uses no edge more than once. An Euler trail uses every edge exactly once; it is open if its endpoints differ. An Euler circuit is an Euler trail whose endpoints agree. A vertex is active if it has positive degree. Isolated vertices do not need to be visited by a trail of positive length.
When there are no edges, we adopt the convention that the length-zero walk at any vertex is an Euler circuit; there is no open Euler trail. The criteria below treat graphs with at least one edge, so their active-vertex subgraph is nonempty.
Theorem 2.2.2
(Euler circuit criterion)
Let have at least one edge. An Euler circuit exists if and only if all active vertices lie in one connected component and every vertex has even degree.
Theorem 2.2.3
(Open Euler trail criterion)
Let have at least one edge. An open Euler trail exists if and only if all active vertices lie in one connected component and exactly two vertices have odd degree. In the open case the odd vertices are its endpoints.
Why degrees must have the stated parity
Proof
(Pairing arrivals with departures)
When a trail passes through a vertex, pair the incidence used to enter with the incidence used to leave. A loop has two incidences at its vertex, one for departure and one for arrival, and hence contributes two to the degree. In a closed trail, arrivals and departures pair at the starting vertex as well. Thus a closed trail using every edge gives even degree at every vertex.
For an open trail from to , all incidences pair except the initial departure from and final arrival at . Hence have odd degree and every other vertex has even degree. Moreover, all vertices incident to edges appear on the trail, so they lie in the same connected component. These arguments establish necessity; they have not yet constructed a trail.
Even degrees let us splice closed trails
Proof
(Extending and splicing closed trails)
Assume all active vertices are connected and every degree is even. Start at any active vertex and walk along unused edges, stopping only when the current vertex has no unused incident edge. The process stops because the graph has finitely many edges.
It cannot stop at a vertex other than . Each time the walk arrives at such a vertex, the number of used incidences there is odd until it leaves; its total degree is even, so an unused incidence remains. Loops count twice and are used as a whole, so they do not change this parity argument. The maximal trail therefore returns to and is closed.
If it uses every edge, it is an Euler circuit. Otherwise remove its used edges temporarily. Every remaining degree is even, because the closed trail used an even number of incidences at each vertex. Connectivity of the original active graph ensures that some vertex on the closed trail is incident to an unused edge: follow an original path from the trail to an unused edge and take the first edge of that path not yet used by the trail.
Start at that vertex and again follow unused edges until no continuation is possible. The same parity argument produces another closed trail, this time using only remaining edges. Insert this new trail into the old one at their common vertex: follow the old trail to the vertex, traverse the new closed trail, then resume the old trail. The result is closed and uses each of its edges once. Each splice uses at least one previously unused edge, so finiteness guarantees that the process terminates only after all edges have been included. This proves sufficiency for a circuit and gives a constructive method.
Proof X-ray
Where each hypothesis is spent
Each hypothesis is spent at one identifiable point. Even degree is used twice, in the same form. A vertex other than the start, once entered, has an odd number of used incidences and hence an unused one, which forces every maximal walk to close up at its start. A closed trail uses an even number of incidences at each vertex, so the leftover graph again has all degrees even and the same argument can be rerun on it. Connectivity of the active vertices is used once per splice, only to guarantee that the current closed trail touches some unused edge; without it the construction stops with edges left in another component, as for the two disjoint triangles below. Finiteness gives termination twice: each walk stops, and each splice consumes at least one new edge. Nothing depends on the starting vertex or on which unused edge is taken, which is why the method is a construction rather than a search.
Worked example 2.2.4
(Splicing two triangles)
Take vertices with edges . There are two triangles sharing only . The degrees are and all other degrees are 2. One closed trail is ; splice the unused closed trail at . The result
uses all six edges once. Repeating is necessary here and is permitted. The walk is an Euler circuit, even though it is not a simple cycle.
Worked example 2.2.5
(Splicing in a loop)
Let have vertices , edges and a loop at . Then and , all even, and is connected. Start at and walk ; on returning to both of its incidences are used, so the walk stops at its start, as the proof predicts. The loop is unused and meets the trail at . Splicing in the closed trail at gives , which uses all four edges once. Had the loop been counted once, would appear to have odd degree and the criterion would wrongly deny the circuit.
Exactly two odd vertices produce an open trail
Proof
(Adding one distinguishable temporary edge)
Now assume the active graph is connected and exactly have odd degree. Add a new temporary edge joining and , even if another edge between them already exists. Their degrees become even, the others remain even, and the active graph stays connected. The circuit result produces a circuit using every original edge and the new edge once.
Rotate the cyclic description of this circuit so that the temporary edge is last, then remove that one edge. The remaining walk uses each original edge exactly once and runs between and , so it is an open Euler trail. The new edge must be marked separately in a multigraph; otherwise deleting an unspecified parallel edge could make the construction ambiguous.
Worked example 2.2.6
(An open trail between the two odd vertices)
In the two-triangle example, add the original edge to the six listed edges. Then are the only odd vertices. A trail from to is
It uses exactly once. The extra edge here is part of the graph; the temporary edge in the proof would be another, separately marked edge.
Counterexample mode
Even degree alone does not connect separate pieces
Two disjoint triangles have all degrees equal to 2, but no single walk can use edges in both components. A graph with an Euler circuit may have isolated vertices, because they have no edges to cover; it may not have two separate components containing edges. The connectivity condition applies to active vertices, not to every vertex indiscriminately.
Common mistake
(A stuck walk is closed, not necessarily complete)
When all degrees are even, walking along unused edges until stuck always returns to the start, but it need not use every edge. In the two-triangle graph the walk stops at with unused. The splice step is part of the construction, not an optional refinement.
Common mistake
(Count a loop twice)
A loop contributes two to the degree of its vertex. In the first exercise below, counting the loop at once would give and : a single odd vertex, which no graph can have. The correct count shows that an Euler circuit exists.
Exercises and solutions
Quick check
(Let have vertices , two distinct edges from to , and a loop at . Decide whether has an Euler circuit, and give one if it does.)
Solution · Answer
The loop counts twice, so and . Both vertices are active and connected. An Euler circuit is . Edge labels distinguish the parallel edges.
Quick check
(For the path , decide whether an Euler circuit or an open Euler trail exists.)
Solution · Answer
For , the degrees are . The active graph is connected and the two odd vertices are , so an open Euler trail exists; the displayed path itself is one. No Euler circuit exists because two degrees are odd.
Quick check
(Does have an Euler circuit or an open Euler trail?)
Solution · Answer
In , each vertex has degree 3, so there are four odd vertices. It has neither an Euler circuit nor an open Euler trail, despite being connected. The two-odd criterion is exact, not merely a suggestion about where to start.
To use the theorem, first specify whether loops and parallel edges are present, count each loop twice, and check connectivity after discarding isolated vertices. Then degree parity determines whether the required edge-exact walk exists.