Euler Trails and Hamilton Cycles
Settle exactly when a graph has a walk using every edge once, and see why the analogous question about vertices has no such clean answer.
What a learner can do afterwards
- State and prove the degree condition for an Euler circuit and for an Euler trail
- Give sufficient conditions for a Hamilton cycle and explain why they are not necessary
- Contrast the two problems in terms of how hard each is to decide
1 · Read
An Euler circuit is a closed walk that uses every edge exactly once. It exists exactly when the graph is connected and every vertex has even degree. Each visit to a middle vertex spends one edge in and one out, so zero odd vertices is both necessary and sufficient.
An Euler trail drops the need to finish where you started. It exists exactly when the graph is connected and holds zero or two odd degree vertices. With two odds, every trail must run from one odd vertex to the other. Adding a temporary edge between the odds turns the trail case into the circuit case.
A Hamilton cycle visits every vertex exactly once and returns to the start. No clean degree test decides it. Rules like Dirac and Ore promise a cycle when they hold, but graphs below their bars can still hold one. Those rules are sufficient but not necessary, and counterexamples prove the gap.
To judge edge covering, count odd degrees and finish in moments. To judge vertex visiting, expect search through an enormous space of routes. Edges are easy to exhaust while vertices are not, so never carry Euler reasoning across to Hamilton.
Count odd degrees for Euler walks, and treat Hamilton cycles as a harder different game.
2 · Watch
Take it off screen
Where it sits
This opens up
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.