Paths, Walks, Trails and Circuits
Brisbane's CityCycle bike-share maintenance crews need to inspect every dock without retracing any segment, that's an Eulerian trail problem. Whether a such a route exists depends entirely on counting odd-degree vertices. This lesson distinguishes walks, trails and paths, then gives you the rule for Eulerian circuits.
Practise this lesson
Three printable worksheets that build from foundations to mastery, or build your own from any module’s questions.
A postman must walk every street in a suburb exactly once and return to the post office. What conditions must the street network satisfy for this to be possible?
Before reading onwrite your gut answer.
An Eulerian circuit exists if and only if every vertex has even degree and the network is connected. An Eulerian trail (not a circuit) exists iff exactly 2 vertices have odd degree.
Walk: any sequence of vertices/edges, can repeat vertices and edges.
Trail: walk with no repeated edges (vertices may repeat).
Path: walk with no repeated vertices (and therefore no repeated edges).
Circuit / Cycle: closed walk (starts and ends at same vertex). Eulerian circuit uses every edge exactly once.
Key facts
- Definitions: walk, trail, path, circuit
- Eulerian circuit: 0 odd-degree vertices
- Eulerian trail: exactly 2 odd-degree vertices
Concepts
- Why even degree allows circuit
- Difference between Eulerian and Hamiltonian
- When a postman problem is solvable
Skills
- Classify walk/trail/path in a network
- Check Eulerian circuit existence
- Find Hamiltonian path by inspection
Consider a network with vertices A, B, C, D and edges A–B, B–C, C–D, D–A, B–D.
- Walk A→B→D→B→C: visits B twice and uses edge B–D, then B–C. Valid walk, no restrictions on repetition.
- Trail A→B→C→D→A: no repeated edges, valid trail. Also a circuit (returns to start).
- Path A→B→C→D: no repeated vertices, valid path.
- A→B→D→A→B is a walk but NOT a trail (edge A–B repeated).
Walk: any sequence of edges (vertices can repeat). Trail: edges not repeated (vertices can repeat). Path: vertices not repeated (hence edges not repeated either). Each is a stricter version of the previous. Paths are the most restrictive.
Pause, copy the walk → trail → path hierarchy: walk (edges and vertices can repeat), trail (edges not repeated; vertices can repeat), path (vertices not repeated; edges automatically not repeated either), and what each restriction removes into your book.
We just saw the hierarchy from walk (anything goes) to trail (no repeated edges) to path (no repeated vertices), each is a stricter version of the previous. That raises a question: a trail avoids repeating edges, when does a trail exist that uses every single edge in the network exactly once? This card answers it → Euler's theorem: an Eulerian circuit (uses every edge, returns to start) exists when all vertices have even degree AND the network is connected; an Eulerian trail (uses every edge, different start and end) exists when exactly two vertices have odd degree.
An Eulerian circuit uses every edge exactly once and returns to the start. It exists if and only if:
- The network is connected (all vertices reachable), AND
- Every vertex has even degree (0 odd-degree vertices).
An Eulerian trail (uses every edge once, different start and end) exists iff:
- The network is connected, AND
- Exactly 2 vertices have odd degree. (Start and end at those two vertices.)
Eulerian circuit: uses every edge exactly once, returns to start, requires ALL vertices to have even degree AND network is connected. Eulerian trail (not circuit): uses every edge once, different start and end, requires exactly 2 odd-degree vertices.
Pause, copy Euler's theorem: all vertices even degree AND network connected → Eulerian circuit exists; exactly 2 vertices odd degree AND connected → Eulerian trail exists; more than 2 odd-degree vertices → no Eulerian trail or circuit is possible into your book.
We just saw Eulerian trails and circuits that visit every edge exactly once, guaranteed by Euler's theorem based on vertex degrees. That raises a question: what if instead you want to visit every vertex exactly once, like a delivery driver who needs to stop at each suburb just once? This card answers it → a Hamiltonian path visits every vertex exactly once (different start/end); a Hamiltonian cycle returns to the start; unlike Euler's theorem, no simple condition guarantees them, you must check by inspection.
A Hamiltonian path visits every vertex exactly once (different start and end). A Hamiltonian cycle visits every vertex exactly once and returns to the start.
Key contrast with Eulerian:
- Eulerian: every edge once. Hamiltonian: every vertex once.
- Euler's theorem gives a simple degree condition. No simple condition exists for Hamiltonian it's identified by inspection for small networks.
For a 4-vertex network A–B–C–D–A (square): Hamiltonian cycle = A→B→C→D→A. Uses every vertex once.
Hamiltonian path visits every vertex exactly once (different start/end). Hamiltonian cycle visits every vertex exactly once and returns to start. No simple theorem guarantees them, must test by inspection. Eulerian = edges once; Hamiltonian = vertices once.
Pause, copy the Hamiltonian path/cycle definitions (Hamiltonian path: every vertex visited exactly once; Hamiltonian cycle: every vertex once then return to start) and the Eulerian-vs-Hamiltonian distinction (Eulerian: every edge once; Hamiltonian: every vertex once) into your book.
Worked examples · reveal each step
Network: A–B, B–C, C–D, D–A, A–C. Classify: (i) A→B→C→A→D (ii) A→C→B→C→D (iii) A→B→C→D
Network with degrees A=4, B=2, C=4, D=2, E=2. Does an Eulerian circuit exist?
Network: A–B, A–C, B–C, B–D, C–D, D–E. Find a Hamiltonian path from A to E.
- A network has vertex degrees 3, 2, 3, 2, 2. Does an Eulerian circuit exist? Does an Eulerian trail exist?
- Give an example of a trail that is NOT a path in a 4-vertex network. Draw the network and label the trail.
- A network has 5 vertices forming a complete graph (every pair connected). Does a Hamiltonian cycle exist? Find one.
- Explain in your own words why an Eulerian circuit requires all even degrees.
For the postman to walk every street exactly once and return: the network must be connected and every intersection must have even degree0 odd-degree vertices means an Eulerian circuit exists. If exactly 2 intersections have odd degree, an Eulerian trail exists (start at one odd vertex, end at the other).
Q1. A trail is best described as a walk in which:
Q2. An Eulerian circuit exists if and only if:
Q3. A connected network has vertex degrees 4, 4, 2, 2, 2. Which of the following is true?
Q4. A Hamiltonian path visits:
Q5. A network has vertex degrees 3, 3, 2, 2. An Eulerian trail (not circuit):
SA 1. A network has 6 vertices with degrees 4, 3, 3, 2, 2, 2. (a) Does an Eulerian circuit exist? (b) Does an Eulerian trail exist? Justify both answers. (2 marks)
SA 2. Explain the key difference between an Eulerian circuit and a Hamiltonian cycle. Give a network where an Eulerian circuit exists but a Hamiltonian cycle is impossible, and explain why. (3 marks)
Answers (click to reveal)
MC 1, B: Trail = no repeated edges.
MC 2, D: Connected + all even degrees → Eulerian circuit.
MC 3, A: All degrees (4,4,2,2,2) are even → Eulerian circuit exists.
MC 4, C: Hamiltonian = every vertex once.
MC 5, B: Exactly 2 odd-degree vertices → Eulerian trail, starting/ending at those vertices.
SA 1: 2 odd-degree vertices [identify: degree-3 vertices] → (a) no circuit [1]; (b) yes trail [1].
SA 2: Clear distinction [1]; valid example [1]; explanation [1].
Timed questions on trails, Eulerian circuits and Hamiltonian paths.
⚔ Enter the arenaMark lesson as complete
Tick when you've finished the practice and review.