Day 66 — Euler & Hamilton

Updated

July 30, 2026

Day 66 — Euler & Hamilton paths

Stage VI · concept day
Goal: Characterize Eulerian circuits/trails; Hierholzer idea; contrast Hamilton paths/cycles with NP-hardness awareness; state Dirac and Ore sufficient conditions.

Why this matters

Euler: traverse every edge exactly once (Chinese Postman, routing inspection).
Hamilton: visit every vertex exactly once (TSP culture).
Euler is easy (degree conditions + linear algorithms). Hamilton is hard in general (NP-complete decision). Knowing which problem you face saves careers.

Theory

Eulerian trails and circuits

In an undirected multigraph:

  • Eulerian circuit (tour): closed trail containing every edge exactly once.
  • Eulerian trail: (possibly open) trail containing every edge exactly once.

Theorem (Euler — undirected).

  1. \(G\) has an Eulerian circuit ⇔ \(G\) is connected (up to isolated vertices) and every vertex has even degree.
  2. \(G\) has an Eulerian trail but not necessarily a circuit ⇔ connected and exactly zero or two vertices of odd degree.
    • Zero odds ⇒ circuit.
    • Two odds ⇒ trail starts at one odd and ends at the other.

Proof sketch (circuit).

  • \((\Rightarrow)\) Enter/leave pairs force even degrees; connectivity for edges.
  • \((\Leftarrow)\) Hierholzer: start at a vertex; build a trail until stuck (must be start if all even); if unused edges remain, they form an even-degree subgraph in a connected component of remainder—splice a detour tour into the main tour; repeat.

Directed version (lite): strongly connected (weakly + balanced) and \(\mathrm{deg}^+=\mathrm{deg}^-\) at every vertex for Eulerian circuit.

Hierholzer’s algorithm (idea)

  1. Start at \(v\); form a closed trail by unused edges until return.
  2. While unused edges: start from a vertex on current tour that has unused edges; form another closed trail; splice.
  3. Result is Eulerian circuit.

Hand-simulate on small multigraphs.

Chinese Postman (lite awareness)

If not all even: add duplicate edges of minimum cost pairing odd-degree vertices (perfect matching on odd set)—then Eulerian. Polynomial for undirected.

Hamiltonian paths and cycles

  • Hamilton path: path visiting every vertex exactly once.
  • Hamilton cycle: cycle through every vertex exactly once.

No simple efficient characterization known (unlike Euler).
Decision problem is NP-complete (for general graphs)—awareness: hard in worst case; small instances solvable by hand/backtrack.

Sufficient conditions (not necessary)

Dirac’s theorem (1952). If \(G\) is simple on \(n\ge 3\) vertices and \(\deg(v)\ge n/2\) for every \(v\), then \(G\) has a Hamilton cycle.

Ore’s theorem (1960). If \(n\ge 3\) and for every pair of nonadjacent vertices \(u,v\), \(\deg(u)+\deg(v)\ge n\), then \(G\) has a Hamilton cycle.

Both imply high connectivity and many edges—strong hypotheses.
Not necessary: \(C_n\) is Hamiltonian but degrees are 2, far below \(n/2\) for large \(n\).

Bipartite Hamilton

\(K_{m,n}\) has Hamilton cycle ⇔ \(m=n\ge 2\).
Hamilton path if \(|m-n|\le 1\).

Relationship summary

Euler Hamilton
Object used once edges vertices
Characterization clean (degrees) none simple
Complexity poly-time NP-complete decide
Classic theorems Euler 1736 Dirac, Ore (sufficient)

TSP culture

Traveling Salesman: min weight Hamilton cycle in weighted complete graph—NP-hard optimization. Metric TSP approximable—awareness only.

Necessity of even degrees (detail)

Proof. In an Eulerian circuit, every time the tour enters a vertex via an edge it must leave via a different edge—pairing the incident edges. Hence degree even at every vertex. At the start/end (same vertex), the first departure and last arrival also pair. For an open Eulerian trail, the start has one unpaired departure and the end one unpaired arrival → exactly those two vertices odd degree. \(\square\)

Handshaking corollary

The number of odd-degree vertices is always even. So the Euler trail condition “0 or 2 odds” is the only possible small counts; 1 or 3 odds can never occur.

Gray codes and hypercubes

The \(n\)-dimensional hypercube \(Q_n\) has a Hamilton path/cycle (for \(n\ge 2\) cycle): binary reflected Gray codes list all \(n\)-bit strings so consecutive codes differ by one bit—exactly a Hamilton path in \(Q_n\). Important for error-resistant coding and hardware state tours.

Worked examples

Example 1 — \(K_2\)

Two verts one edge: Eulerian trail yes; circuit no (odds). Not Hamilton cycle (\(n<3\)).

Example 2 — \(C_n\)

Eulerian circuit (2-regular even); Hamilton cycle (itself).

Example 3 — \(K_4\)

Degrees 3 (odd): no Euler circuit; all deg odd (4 vertices odd)—no Euler trail either? Four odds: no Euler trail (need 0 or 2 odds). Hamilton: yes (\(K_n\) for \(n\ge 3\) Hamiltonian).

Example 4 — House graph

Square with roof triangle: check degrees for Euler; often one trail.

Example 5 — Hierholzer

Two edge-disjoint cycles sharing a vertex: tour one cycle, splice the other at shared vertex.

Example 6 — Exactly two odds

Path \(P_n\): two odds (ends); Eulerian trail = the path itself if no extra edges; actually \(P_n\) has \(n-1\) edges, trail visits all edges yes.

Example 7 — Dirac applies

\(K_n\) degrees \(n-1\ge n/2\) for \(n\ge 2\)—has Hamilton cycle for \(n\ge 3\).

Example 8 — Dirac fails hypothesis but Hamilton

\(C_5\): deg \(2<2.5\); still Hamilton. Dirac not necessary.

Example 9 — Ore check

Graph: nonadjacent pair with deg sum \(<n\) may still be Hamiltonian—Ore sufficient only.

Example 10 — \(K_{2,3}\)

No Hamilton cycle (unequal parts). Hamilton path: yes (start in size 3).

Example 11 — Petersen graph awareness

Famous non-Hamiltonian 3-regular graph—optional name.

Example 12 — Directed Euler

Cycle digraph: balanced, Eulerian circuit.

Example 13 — Add edge for Euler

Two odds: add edge between them (if missing) creates Euler circuit in multigraph sense—Chinese postman pair.

Example 14 — Complete bipartite equal

\(K_{3,3}\): Hamilton cycle alternates parts.

Example 15 — Complexity contrast

Checking all degrees even: \(O(n)\). Searching Hamilton: exponential naive \(n!\).

Example 16 — Degree table diagnosis

Graph degrees \((2,2,2,2,4)\): all even → Euler circuit if connected. Degrees \((3,3,2,2,2)\): two odds → Euler trail. Degrees \((3,3,3,3)\): four odds → no Euler trail; Chinese postman pairs into two paths’ worth of duplicates.

Example 17 — Ore fails, still Hamiltonian

\(C_6\): nonadjacent vertices can have deg sum \(2+2=4<6\); Ore hypothesis fails; still Hamiltonian.

Example 18 — Hierholzer narrative

Multigraph: vertices \(A,B,C\); double edges \(AB\) and cycle \(A{-}B{-}C{-}A\). Start at \(A\), tour \(A{-}B{-}C{-}A\); residual double edge \(AB\) unused—at \(A\) or \(B\) on tour, splice \(A{-}B{-}A\) detour. Full Euler circuit uses every edge.

Example 19 — \(K_{m,n}\) Hamilton summary

Relation Hamilton path Hamilton cycle
\(m=n\ge 2\) yes yes
\(|m-n|=1\) yes no
\(|m-n|\ge 2\) no no

Example 20 — Eulerian but not Hamiltonian

Two copies of \(C_4\) sharing a single vertex: all degrees even (shared vertex deg 4); Eulerian circuit exists; no Hamilton cycle (cannot visit all vertices of both lobes in one cycle without repeating the cut vertex improperly—standard bowtie/barbell-with-point).

Exercises

  1. State Euler circuit theorem fully.
  2. State Euler trail theorem.
  3. Which of \(K_3,K_4,K_5\) have Euler circuits? Euler trails?
  4. \(K_{2,3}\) Euler? Hamilton path/cycle?
  5. Prove necessity of even degrees for Euler circuit.
  6. Hierholzer on a multigraph with 6 edges you draw.
  7. Four odd-degree vertices: can you have Euler trail? What about open Chinese postman?
  8. Define Hamilton path/cycle.
  9. Show \(K_n\) (\(n\ge 3\)) is Hamiltonian.
  10. Apply Dirac to a 6-vertex 3-regular graph—does hypothesis hold?
  11. Give counterexample to converse of Dirac.
  12. Ore: verify or refute on a small graph.
  13. Why \(K_{1,3}\) has no Hamilton path? (It does: path through 3 leaves? Star \(K_{1,3}\) has 4 verts: path leaf-center-leaf leaves one leaf—no Hamilton path.)
  14. \(K_{1,3}\) is a tree—Hamilton path ⇔ tree is a path.
  15. CS: garbage truck routing ~ Euler/Chinese postman.
  16. CS: TSP ~ Hamilton.
  17. Directed: state Euler circuit condition.
  18. Find an Euler trail in a graph with exactly two odds.
  19. True/false: every Eulerian graph is Hamiltonian. (False: two cycles sharing a vertex.)
  20. True/false: every Hamiltonian graph is Eulerian. (False: \(C_n\) with a chord may break even degrees.)
  21. Challenge: prove that if all degrees even and connected, an Euler circuit exists (expand Hierholzer).
  22. Count edge tours? Hard—skip.
  23. Hamilton in hypercube \(Q_n\): yes (Gray codes).
  24. NP-complete awareness: what does “no known poly algorithm” mean practically?
  25. Portfolio: one Euler diagnosis + one Dirac/Ore application writeup.

CS connection

  • Network traversal / street sweeping / DNA fragment assembly (Euler in de Bruijn graphs).
  • TSP / vehicle routing (Hamilton hard).
  • De Bruijn sequences via Euler circuits in digraphs.
  • Compiler / FSM: state tours rare; edge coverage testing ~ Euler culture.
  • Gray codes as Hamilton paths in hypercubes.

Common pitfalls

Pitfall What to do instead
Euler vs Hamilton confusion Edges vs vertices
Ignoring connectivity for Euler Require connected (ignore isolates)
Treating Dirac as necessary Only sufficient
“Hard” means impossible Means computational difficulty
Multigraph degrees for Euler Allowed and natural

Checkpoint

  • Euler circuit/trail iff conditions
  • Hierholzer idea
  • Hamilton definitions
  • Dirac and Ore statements
  • Complexity contrast one sentence
  • Exercises 1–15
  • \(K_{m,n}\) Hamilton rule

Two personal takeaways:

  1. …
  2. …

Selected mini-solutions

  1. \(K_3\): Euler yes (deg 2); \(K_4\) deg 3 no circuit no trail (4 odds); \(K_5\) deg 4 circuit yes.
  2. Degrees 3,3,2,2,2: two odds—Euler trail yes; Hamilton path yes; cycle no.
  3. Star \(K_{1,3}\): no Hamilton path.
  4. False.
  5. False.

Deepening notes

Degree parity quick tests

# odd-degree verts Euler?
0 circuit (if connected)
2 trail start/end at odds
>2 even no trail

Always even count by handshaking—never 1,3,5 odds.

Hierholzer splice picture

Tour \(T\) closed; at vertex \(v\) on \(T\) with unused edge, build tour \(T'\) in residual; replace \(v\) in \(T\) by \(T'\). Edges of \(T\cup T'\) used once.

Dirac/Ore memory

Dirac: every deg ≥ \(n/2\).
Ore: every nonedge \(uv\) has \(\deg u+\deg v\ge n\).
Both sufficient for Hamilton cycle; \(C_n\) shows not necessary.

Extra drills

D1. Euler status of \(K_{2,4}\).
D2. Hierholzer on two squares sharing a vertex.
D3. Hamilton path in \(K_{2,3}\).
D4. Does Dirac apply to \(K_{3,3}\)? (\(n=6\), deg 3≥3 yes—has cycle.)
D5. Ore fail example still Hamiltonian.
D6. Four odds: Chinese postman needs min pairing.
D7. Hypercube \(Q_3\) Hamilton cycle (Gray).
D8. Explain NP-complete for a non-theorist in 3 sentences.

Flash

Euler: even degrees; Hamilton: hard; Dirac \(\deg\ge n/2\); \(K_{m,n}\) cycle iff \(m=n\ge 2\).

Exam drill block

E1. Euler circuit/trail status for \(K_2,K_3,K_4,K_5,C_n,K_{2,3}\).
E2. Hierholzer narrative on a 2-cycle multiedge pair of loops figure.
E3. Prove necessity of even degrees for Euler circuit.
E4. Dirac: does it apply to \(K_{n,n}\)? Degrees \(n\) vs \(2n/2=n\)—yes equality; has cycle.
E5. Ore statement; give \(C_5\) as converse fail.
E6. Hamilton path/cycle in \(K_{3,3}\) and \(K_{2,3}\).
E7. Chinese Postman idea for two odds.
E8. TSP vs Hamilton decision—one sentence each.
E9. Why “Eulerian ⇒ Hamiltonian” is false (bowtie).
E10. Gray code = Hamilton path in \(Q_n\) awareness.

Mini solutions

E1. See theory table; \(K_4\) no trail; \(K_5\) circuit; \(K_{2,3}\) trail yes cycle no.
E6. \(K_{3,3}\) both; \(K_{2,3}\) path yes cycle no.
E9. Two triangles sharing a vertex: Eulerian if multigraph degrees even—use two cycles share vertex all even degrees Euler but not Hamilton if… standard: two \(K_3\) sharing vertex has Euler circuit in multigraph sense? Degrees 2,2,2,4,2,2—Euler yes; Hamilton visits all 5 verts hard—actually has no Hamilton cycle. Good.

Deep dive — Choosing the model

English Graph object Complexity vibe
Inspect every road Euler trail/circuit Easy (degrees)
Visit every city once Hamilton path/cycle Hard (NP-c)
Revisit roads OK, min length Chinese postman Poly undirected
Revisit cities OK, min length Metric TSP etc. Hard

Mislabeling “tour the neighborhood streets” as TSP is a classic modeling error—streets are edges (Euler), landmarks are vertices (Hamilton).

Synthesis

Euler cares about edges and degrees; Hamilton cares about vertices and has no simple iff criterion—only sufficient conditions (Dirac, Ore) and hardness. Hierholzer constructs Euler circuits by splicing tours. Bipartite Hamilton needs balanced parts for cycles. Always diagnose odd-degree counts first for edge tours.

S1. Full Euler diagnosis for \(K_{2,4}\) and \(K_{3,3}\).
S2. Prove necessity of even degrees for an Eulerian circuit (paragraph proof).
S3. Apply Dirac carefully to a 3-regular graph on 6 vertices—hypothesis? Hamilton?
S4. Explain why four odd-degree vertices forbid an Euler trail but allow a Chinese-postman pairing approach.
S5. Write a 5-sentence contrast of Euler vs Hamilton for a non-math stakeholder.

Tomorrow

Day 67 — Coloring & planarity: chromatic number; clique bound; 4-color theorem; Kuratowski/Wagner awareness; register allocation story.