Eulerian circuits and Hamiltonian cycles
Separate visiting every edge from visiting every vertex, prove the Euler parity criterion, and use Hamiltonian obstructions carefully.
On this page
The question for today
What you’ll understand
- Apply the connected-support and degree conditions for Euler trails.
- Explain the cycle-splicing proof of the Euler circuit theorem.
- Distinguish necessary Hamiltonian conditions from sufficient criteria.
Two route questions sound almost identical: traverse each connection once, or visit each location once. Their mathematical behavior differs sharply. Eulerian routes constrain edge usage and admit a complete parity test. Hamiltonian routes constrain vertex usage and generally require deeper search or stronger hypotheses. A correct model names which resources may repeat and whether the route must return to its starting point.
An edge-covering route pairs arrivals and departures
An Euler trail uses every edge exactly once; an Euler circuit is such a trail that finishes where it starts. Vertices may repeat. For a finite undirected graph with at least one edge, an Euler circuit exists exactly when all non-isolated vertices lie in one connected component and every vertex has even degree. The connected-support condition allows irrelevant isolated vertices, but it forbids two separated edge-bearing components. At each visited vertex, entering and leaving pair its incident edge usages.
For a nonclosed Euler trail, only the start and finish can have an unmatched incident usage, so exactly two vertices have odd degree. Conversely, if the edge-bearing support is connected and exactly two vertices are odd, add an auxiliary edge between them, obtain an Euler circuit in the resulting multigraph, and remove the auxiliary edge to produce an open trail. With no edges, the trivial length-zero circuit is a convention that can be handled separately rather than hidden in a connectivity condition.
Why even degrees suffice
Start at an incident vertex and follow unused edges until no continuation remains. With all degrees even, getting stuck anywhere other than the start is impossible: arriving there would leave an odd number of already-used incidences and therefore at least one unused edge. The route closes. If it has not used every edge, connectedness of the support ensures some vertex of the current closed trail is incident with an unused edge, possibly by considering a path toward an unused edge.
Starting at that vertex, repeat the process using only unused edges. Removing a closed trail preserves even residual degrees, so this new trail also closes and can be spliced into the old one. Each splice consumes additional edges, and finiteness guarantees termination. This argument supplies both a proof and the outline of an algorithm. Parity is not merely a quick rejection test here; coupled with the support condition, it is a complete existence certificate.
A vertex-covering cycle obeys different rules
A Hamiltonian cycle in a simple graph is a cycle of length at least three containing every vertex exactly once, apart from repeating the first vertex to close it. Every vertex must have degree at least two, but that is not sufficient. Two triangles sharing just one vertex have minimum degree two and an Euler circuit, yet no Hamiltonian cycle: removing the shared vertex disconnects the graph, whereas deleting one vertex from a Hamiltonian cycle leaves a spanning path among all remaining vertices.
There are useful sufficient criteria. Dirac's theorem states that a finite simple graph with vertices and minimum degree at least has a Hamiltonian cycle. It does not say smaller minimum degree forbids one: a long cycle itself is Hamiltonian with degree two. We state this theorem without proving it here. In practice, a displayed cycle certifies a positive result, while a cut vertex or other rigorous obstruction may certify a negative one; failure to find a route is not itself such a certificate.
Work it through
Two triangles sharing a junction
Let the edges be on five vertices. Determine whether the graph has an Euler circuit and whether it has a Hamiltonian cycle.
Vertex a has degree four and b,c,d,e each have degree two. All vertices with edges are connected, so the Euler circuit criterion applies.
The route a–b–c–a–d–e–a uses each of the six edges exactly once and returns to a. Repeating a is allowed for an Euler circuit.
Delete a. The remaining edges bc and de lie in different components. If there had been a Hamiltonian cycle, deleting a from that cycle would have left one path visiting all four remaining vertices, a contradiction.
The graph is Eulerian but not Hamiltonian, despite every vertex having even degree and degree at least two.
The living notebook
Explore the model
Interactive lab · modular
A deterministic cycle visits vertices
Pause and Reset, then set m = 6 and a = 1. Predict the modular walk visits each residue exactly once before returning; Step six times. Reset and set both m = 6 and a = 2, then compare its three-vertex orbit. These are directed modular cycles. They illustrate vertex visitation, not an algorithm for deciding Hamiltonicity or the undirected Euler criterion.
- Residue r0
- 0
- Orbit period · m/gcd(m,a)
- 12
- Distinct residues visited
- 1 of 12
Addition modulo m starts at zero: rₙ = na mod m. Playback advances two additions per second. The orbit has period m/gcd(m,a), including period one for a = 0. This is not a cryptographic security test or a primality algorithm. Parameter changes pause playback and recompute the model at the current elapsed time. Reset restores both parameters and returns time to zero. Playback starts paused. Adjust either parameter, then choose Play or Step.
Look forA closed route can visit only part of the vertex set; inspect coverage as well as return to the start.
Pause & reason
Check your understanding
Your turn
Try it yourself
For the complete graph , determine whether an Euler circuit, an open Euler trail, and a Hamiltonian cycle exist. Explain each answer with a condition or an explicit witness.
Take a moment to make a prediction or work it out on paper. Open a hint when you need one.
Give me a hint
Each vertex has three neighbors. Count the odd-degree vertices, then write a cycle through the four distinct labels.
Compare with the solution
All four vertices have degree three, so there are four odd vertices. An Euler circuit requires zero odd vertices and an open Euler trail requires exactly two, hence neither exists. Label the vertices a,b,c,d. The cycle a–b–c–d–a is Hamiltonian because all its edges belong to the complete graph and it visits every vertex once before returning. This example reverses the worked example: Hamiltonian coverage does not ensure Eulerian coverage.
Keep the idea
Take it with you
- Euler routes use every edge once and may revisit vertices.
- Connected edge-bearing support plus even degrees exactly characterizes Euler circuits.
- Hamiltonian cycles visit every vertex once; degree and cut conditions need separate reasoning.
Read further
Original sources and deeper explanations to follow at your own pace.
Optional progress, saved in this browser when available. Revisit any lesson at any time.
Lesson not marked complete.