4.4Euler and Hamilton paths and circuits
The idea
An Euler circuit uses every edge exactly once and returns to the start. A Hamilton cycle visits every vertex exactly once. They sound alike but behave very differently.
Think of it like this: A postman must walk every street (Euler); a tourist must visit every town (Hamilton).
Why it exists
Euler has an exact test via degrees; Hamilton has none, so questions use specific graphs or sufficient conditions.
How it works
- Euler circuit: connected and every degree even. Euler path: exactly 0 or 2 odd vertices.
- K_n has an Euler circuit iff n is odd.
- A Hamilton cycle has no simple test (NP-complete). Dirac: min degree ≥ n/2 is enough.
- K_n (n ≥ 3) has (n−1)!/2 Hamilton cycles; a bipartite graph with unequal sides has none.
Worked example: Is there an Euler circuit in K₅?
Every vertex has degree 4 (even) and the graph is connected, so yes. K₄ has all degrees 3 (odd), so no.
Now play with it
- →Load K₅: it has both an Euler circuit and a Hamilton cycle.
- →Load the cube Q₃: no Euler path (all degrees 3), but a Hamilton cycle exists.
| Euler | Hamilton | |
|---|---|---|
| Visits every… | edge exactly once | vertex exactly once |
| Exact test? | yes: connected + degree parity | no (NP-complete) |
| Circuit | all degrees even | cycle through all vertices |
| Path | exactly 2 odd vertices | path through all vertices |
| K_n | circuit iff n odd | always (n ≥ 3) |
| Sufficient test | - | Dirac: δ ≥ n/2; Ore |
Seven bridges of Königsberg: four odd vertices, so no Euler path.
Check yourself
A connected graph has exactly 2 vertices of odd degree. It has
Exam notes (the dense version)
An Euler circuit uses every edge exactly once and returns: connected and every degree even. An Euler path exists iff exactly 0 or 2 vertices have odd degree. A Hamilton cycle visits every vertex once; there is no clean criterion (NP-complete). Sufficient: Dirac δ ≥ n/2; Ore deg u + deg v ≥ n for non-adjacent pairs. K_n (n ≥ 3) has (n−1)!/2 Hamilton cycles. A bipartite graph with unequal sides has no Hamilton cycle.
Previous year questions: Graph Theory (24)
PYQs are grouped by topic, so this is the full set for Graph Theory; try the ones that match this subtopic. Open all 24 on the topic page.