← Graphs and Networks › Euler Trails and Hamiltonian Paths
Euler Trails and Hamiltonian Paths
Key Terms
- Euler trail
- a trail that uses every edge exactly once
- Euler circuit
- an Euler trail that starts and ends at the same vertex
- Euler circuit exists ⇔ all vertices have even degree
- Euler trail (not circuit) exists ⇔ exactly two vertices have odd degree (start and end there)
- Hamiltonian path
- a path that visits every vertex exactly once
- Hamiltonian cycle
- a Hamiltonian path that returns to the starting vertex
- No simple condition exists for Hamiltonian paths — must check by inspection
Euler conditions:
• All even degrees → Euler circuit exists
• Exactly 2 odd degrees → Euler trail exists (start/end at odd-degree vertices)
• 4 or more odd-degree vertices → no Euler trail or circuit
Key distinction:
Euler: every EDGE once
Hamiltonian: every VERTEX once
• All even degrees → Euler circuit exists
• Exactly 2 odd degrees → Euler trail exists (start/end at odd-degree vertices)
• 4 or more odd-degree vertices → no Euler trail or circuit
Key distinction:
Euler: every EDGE once
Hamiltonian: every VERTEX once
Worked Example: Graph with edges AB, BC, CD, DA, AC, BD. Find the degree of each vertex and determine if an Euler circuit, Euler trail, or Hamiltonian cycle exists.
deg(A) = 3 (AB, DA, AC), deg(B) = 3 (AB, BC, BD), deg(C) = 3 (BC, CD, AC), deg(D) = 3 (CD, DA, BD)
All 4 vertices have odd degree → no Euler trail or circuit
Hamiltonian cycle: A → B → C → D → A (uses edges AB, BC, CD, DA) → yes, exists
deg(A) = 3 (AB, DA, AC), deg(B) = 3 (AB, BC, BD), deg(C) = 3 (BC, CD, AC), deg(D) = 3 (CD, DA, BD)
All 4 vertices have odd degree → no Euler trail or circuit
Hamiltonian cycle: A → B → C → D → A (uses edges AB, BC, CD, DA) → yes, exists
Hot Tip: The “Seven Bridges of Königsberg” problem (1736) is the origin of graph theory. Königsberg’s bridges form a graph where all vertices have odd degree — Euler proved it impossible to cross each bridge exactly once. This is why the conditions are named after him.
Euler Trails and Circuits
An Euler trail is a route through a graph that uses every edge exactly once. Think of it as: can a street-sweeper travel every road in a city exactly once?
An Euler circuit is an Euler trail that returns to the starting vertex.
Euler’s famous theorem:
- An Euler circuit exists if and only if the graph is connected and every vertex has even degree.
- An Euler trail (non-circuit) exists if and only if the graph is connected and has exactly two vertices with odd degree. The trail must start at one odd-degree vertex and end at the other.
The reasoning: at each “internal” vertex on a trail, you enter and leave the same number of times — requiring even degree. At the start and end vertices of a non-circuit trail, you leave one more time than you enter (or enter one more time than you leave) — requiring odd degree.
Hamiltonian Paths and Cycles
A Hamiltonian path visits every vertex exactly once. A Hamiltonian cycle visits every vertex exactly once and returns to the start.
Unlike Euler trails, there is no simple condition for Hamiltonian paths — you generally have to check by trial and error. This is one of the most famous unsolved problems in computer science (the Travelling Salesman Problem is related).
Strategy for Exam Questions
- List the degree of every vertex
- Count vertices with odd degree
- 0 odd-degree vertices → Euler circuit; 2 → Euler trail; 4+ → neither
- For Hamiltonian: try to find a route by inspection
Strategy: Euler = edges. Hamiltonian = vertices. One letter difference, completely different concept. Write this on your notes page.
Mastery Practice
- Fluency A graph has vertices A, B, C, D with degrees: deg(A) = 2, deg(B) = 2, deg(C) = 2, deg(D) = 2. Does an Euler circuit exist? Does an Euler trail (non-circuit) exist?
- Fluency A graph has vertices P, Q, R, S, T with degrees: deg(P) = 3, deg(Q) = 2, deg(R) = 3, deg(S) = 2, deg(T) = 2. Does an Euler trail exist? If so, where must it start and end?
- Fluency Graph with edges AB, BC, CA, CD, DE, EF, FD. Find the degree of each vertex and determine whether an Euler circuit or trail exists.
- Fluency For the graph: vertices A, B, C, D, E with edges AB, BC, CD, DE, EA. Does a Hamiltonian cycle exist? Identify one if it does.
- Understanding A graph has vertices A, B, C, D, E, F with edges AB, AC, BD, BE, CD, CE, DF, EF.
- (a) Find the degree of each vertex.
- (b) Does an Euler circuit exist? Explain.
- (c) Does an Euler trail exist? If so, find one.
- Understanding A town has a park with 5 locations (A–E) connected by paths: AB, AC, BC, BD, CD, DE. A groundskeeper wants to inspect every path exactly once and return to the start.
- (a) Is this possible? Justify using degree analysis.
- (b) If not, what is the minimum number of paths that must be walked twice to complete the circuit?
- Understanding Determine whether each graph described has an Euler circuit, Euler trail, or neither:
- (a) K4 (complete graph on 4 vertices)
- (b) K5 (complete graph on 5 vertices)
- (c) A cycle graph C6 (hexagon: 6 vertices in a single cycle)
- Understanding Graph: vertices A, B, C, D, E, F with edges AB, BC, CD, DE, EF, FA, AC, CE, EA.
- (a) Find all vertex degrees.
- (b) Find an Euler trail or circuit if one exists.
- (c) Does a Hamiltonian cycle exist?
- Problem Solving A delivery driver must travel every road in a network exactly once and return to the depot. The network has vertices (intersections) A, B, C, D, E, F with edges: AB, AC, AD, BC, CD, CE, DE, EF, BF. Determine if a route exists and, if so, find one starting at A.
- Problem Solving A connected graph has 8 vertices. Two of the vertices have degree 3, and the remaining six have degree 2.
- (a) How many edges does the graph have?
- (b) Does an Euler trail exist? Does an Euler circuit exist? Explain.
- (c) Does a Hamiltonian cycle necessarily exist? Justify your reasoning.