Euler and Hamilton paths
Euler and Hamilton paths study the existence and construction of trails/circuits that visit every edge once (Euler) or every vertex once (Hamilton) in graphs, with simple tests, algorithms (Hierholzer) and sufficient theorems (Dirac, Ore).
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Graph models appear in routing, PCB track design, network maintenance and travelling-salesman variants. Engineers use Euler paths to plan routes that traverse every connection (edge) exactly once (useful in inspection, wiring, PCB milling) and use Hamilton paths/cycles in problems that require visiting every node once (job scheduling, some routing and layout problems). Understanding when such paths exist and how to find them is essential for design and optimization.
Key ideas
Start with basic definitions and exact theorems used in exams.
Graph: a pair G = (V, E) where V is a finite set of vertices and E is a set of unordered pairs (for undirected) or ordered pairs (for directed) of vertices called edges. (Used everywhere below.)
Degree: for an undirected graph, the degree deg(v) of a vertex v is the number of edges incident to v; loops count twice. For directed graphs, outdegree outdeg(v) and indegree indeg(v) count outgoing and incoming directed edges respectively. A directed loop at v contributes 1 to both indeg(v) and outdeg(v).
Trail: a trail is a walk that does not repeat an edge.
Euler trail (Euler path): a trail that uses every edge of the graph exactly once.
Euler circuit (Euler cycle): an Euler trail that starts and ends at the same vertex.
Hamiltonian path: a simple path that visits every vertex exactly once.
Hamiltonian cycle (Hamiltonian circuit): a Hamiltonian path that starts and ends at the same vertex.
Connected graph: an undirected graph is connected if there is a path between every pair of vertices. For directed graphs we use strongly connected when every vertex reaches every other by directed paths, and weakly connected when the underlying undirected graph is connected.
Key theorems (exact statements as usually required):
Handshaking lemma (assumption: finite undirected graph G = (V,E)): sum of degrees equals twice the number of edges: sum_{v in V} deg(v) = 2·|E|. Consequence: the number of vertices of odd degree is even.
Euler's theorem for undirected graphs (assumptions: finite undirected connected graph; isolated vertices with zero edges are a special case):
- G has an Euler circuit if and only if G is connected (ignoring isolated vertices) and every vertex has even degree.
- G has an Euler trail (but not a circuit) if and only if G is connected (ignoring isolated vertices) and exactly two vertices have odd degree (these two are the endpoints of every Euler trail).
Proof idea (common exam derivation): necessity follows from counting edge-entries and exits at a vertex along a trail (parity argument). Sufficiency: construct an Euler circuit by Hierholzer's algorithm (build a cycle, then repeatedly splice in cycles until all edges used). For the trail case, add an extra edge between the two odd vertices to make degrees even, find an Euler circuit, then remove the added edge to obtain an Euler trail.
Euler criteria for directed graphs (assumptions: finite directed graph G; connectivity requirements as stated below):
- G has a directed Euler circuit iff G is strongly connected when restricted to vertices of nonzero degree (or its underlying undirected graph is connected) and for every vertex v, indeg(v) = outdeg(v).
- G has a directed Euler trail (but not a circuit) iff the underlying undirected graph is connected (on non-isolated vertices) and exactly one vertex has outdeg(v) − indeg(v) = 1 (start), exactly one has indeg(v) − outdeg(v) = 1 (end), and all others satisfy indeg(v) = outdeg(v).
Hamiltonian sufficient conditions (no simple iff test exists; these are commonly required theorems):
- Dirac's theorem (assumptions: simple graph G with n = |V| ≥ 3): if for every vertex v, deg(v) ≥ n/2, then G is Hamiltonian.
- Ore's theorem (assumptions: simple graph G with n = |V| ≥ 3): if for every pair of distinct non-adjacent vertices u,v, deg(u) + deg(v) ≥ n, then G is Hamiltonian.
Note: These are sufficient but not necessary conditions. Determining existence of a Hamiltonian cycle in an arbitrary graph is NP-complete (decision problem); you may be asked to show membership or reference this in higher-level courses.
How to draw diagrams in answers (exact instructions):
- For degree checks and Euler proofs: draw the graph with vertices labelled (e.g., A,B,C...) and edges as straight lines. Mark degrees next to each vertex. If proving Euler sufficiency by Hierholzer, draw the initial cycle in a different colour or dashed line, then show a second cycle and exactly where you splice it (draw an insertion point vertex label and arrows indicating the splice), finally show the merged circuit.
- For Hamiltonian examples: draw the graph and attempt to trace a path visiting all vertices; show failed attempts by crossing edges used twice.
Where exam derivations are asked, give the parity reasoning for Euler, and for Dirac give the classical contradiction proof: assume no Hamiltonian cycle, take a longest path and use degree bounds to derive a closure that forces a cycle including all vertices.
Formulas
sum_{v in V} deg(v) = 2 · |E| — sum of degrees equals twice the number of edges; deg(v) is unitless; applies to finite undirected graphs.
(G connected) and (forall v, deg(v) is even) ⇔ G has an Euler circuit — deg in integer counts, applies to finite undirected graphs with connectivity on vertices with nonzero degree.
(G connected) and (exactly two vertices have odd degree) ⇔ G has an Euler trail (but not circuit) — integer counts; applies to finite undirected graphs.
forall v, indeg(v) = outdeg(v) and G (on nonzero-degree vertices) strongly connected ⇒ directed Euler circuit exists — indeg/outdeg are counts; applies to finite directed graphs.
If G simple, n ≥ 3 and forall v, deg(v) ≥ n/2 ⇒ G is Hamiltonian (Dirac) — deg unitless; sufficient condition only.
If G simple, n ≥ 3 and for every non-adjacent u,v, deg(u)+deg(v) ≥ n ⇒ G is Hamiltonian (Ore) — deg unitless; sufficient condition only.
Worked examples
Example 1 — Decide Euler trail/circuit (theory-model answer expected in exams): Graph G with V = {1,2,3,4,5} and E = {12, 23, 34, 41, 15}. (Draw five vertices labelled 1..5 placed roughly as a square with 5 attached to 1.) Steps:
- Compute degrees: deg(1)=3 (edges 12,41,15), deg(2)=2, deg(3)=2, deg(4)=2, deg(5)=1.
- Count odd-degree vertices: vertices 1 and 5 are odd (deg 3 and 1). There are exactly two odd vertices.
- Check connectivity: graph is connected (path exists between any pair).
- By Euler's theorem, G has an Euler trail (starts at vertex 1 and ends at vertex 5 or vice versa) but no Euler circuit. Answer: The graph has an Euler trail between vertices 1 and 5. (Show a possible trail: 5–1–2–3–4–1 uses each edge once.)
Example 2 — Trace Hierholzer's algorithm (constructive example): Graph: two triangles sharing vertex A. V={A,B,C,D,E}. E={A-B, B-C, C-A, A-D, D-E, E-A} (draw two triangles ABC and ADE meeting at A). Goal: find an Euler circuit (all degrees even: deg(A)=4, others deg=2). Steps (numbered):
- Start at A. Find a cycle: A–B–C–A. Record cycle C1 = [A,B,C,A]. Mark edges used.
- Check if any unused edges remain. Yes: edges A–D, D–E, E–A.
- Find a vertex on C1 that has unused incident edges: choose A. From A find cycle C2 = [A,D,E,A].
- Splice C2 into C1 at A: result circuit = [A,D,E,A,B,C,A]. This visits every edge once. Show final circuit and show that all edges used. Final answer (bold): Euler circuit exists; one Euler circuit is A–D–E–A–B–C–A.
Example 3 — Use Dirac's theorem (short answer style): Given a simple graph G with n=6 vertices and degrees {3,3,4,3,3,4}. Check: for every vertex deg(v) ≥ n/2 = 3. Hence by Dirac's theorem G is Hamiltonian. State conclusion and briefly note that Dirac is only sufficient: you may still find Hamiltonian cycles by search.
Also show a counterexample where Euler exists but Hamiltonian does not: two triangles sharing a vertex (example 2). It is Eulerian (all degrees even) but it is not Hamiltonian because any cycle that returns to the shared vertex must repeat it or miss vertices; show failed attempt and conclude no Hamiltonian cycle.
Common mistakes
- Confusing necessary and sufficient conditions: Dirac/Ore are sufficient but not necessary for Hamiltonian cycles — do not claim the converse.
- For directed Euler: failing to check the weak/strong connectivity condition of the underlying graph when applying indeg=outdeg.
- Trying to apply Euler degree tests to determine Hamiltonicity — they are unrelated properties in general.
For your exam
Kinds of questions:
- Short definitions: define Euler trail, Euler circuit, Hamiltonian path, Hamiltonian cycle (expect bold, precise statements).
- Short proofs/derivations: prove the handshaking lemma; prove necessity in Euler theorem (parity). Provide Hierholzer algorithm steps for sufficiency.
- Diagram problems: given a drawn graph, compute degrees, decide Euler/Hamiltonian, and produce an Euler trail or argue non-existence of Hamiltonian cycle. Draw the graph, label degrees, show the route if it exists.
- Theorem application: apply Dirac or Ore to show existence of a Hamiltonian cycle, or show these conditions do not hold and try counterexamples.
- Algorithm trace: trace Hierholzer's algorithm step-by-step on a given graph.
What a full-marks answer includes:
- Clear definitions (bold terms), drawn and labelled diagram if required.
- Correct degree counts and statement of connectivity (state whether you ignore isolated vertices).
- Correct application of the appropriate theorem and a constructive route (Euler trail/circuit) when required — show every step of Hierholzer if constructing.
- For Hamiltonian questions, either a complete vertex-once path or a rigorous reason why none exists; if using Dirac/Ore, state assumptions (simple, n≥3) and conclude.
Quick check
- In an undirected connected graph, can there be exactly three vertices of odd degree? Yes or No.
- State Dirac's theorem in one sentence (assumptions + conclusion).
- For directed graphs, what equalities on indegree/outdegree are needed for an Euler circuit? Answers: 1. No — number of odd-degree vertices is even by the handshaking lemma. 2. If G is a simple graph with n ≥ 3 and every vertex has degree at least n/2, then G has a Hamiltonian cycle (Dirac's theorem). 3. For every vertex v, indeg(v) = outdeg(v), and the graph is strongly connected on vertices of nonzero degree (or underlying undirected graph is connected).
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?