Mathematics Standard • Year 12 • Module 5 • Lesson 4
Eulerian Trails and Circuits — Skill Drill
Build fluency in applying the degree-based test for Eulerian circuits and trails, and in finding a valid traversal.
1. Quick recall
Answer each question in the space provided. 1 mark each
Q1.1 Complete the conditions:
Eulerian circuit: connected AND every vertex has __________ degree.
Eulerian trail: connected AND exactly ____ vertices have __________ degree.
Q1.2 For an Eulerian trail, you must start at one ___-degree vertex and end at the other ___-degree vertex.
Q1.3 The Königsberg bridge network had 4 vertices, each of degree __________ (all odd). State whether an Eulerian circuit OR trail exists: __________
2. Worked example — does this network have an Eulerian trail or circuit?
Problem. Network with vertices A, B, C, D, E and edges AB, BC, CD, DE, EA, AC, BD. Decide whether an Eulerian circuit or trail exists, and find one if it does.
Step 1 — Confirm the network is connected.
From A you can reach B, C, D, E. ✓ Connected.
Step 2 — Compute the degree of every vertex.
deg(A) = 3 (AB, EA, AC)
deg(B) = 3 (AB, BC, BD)
deg(C) = 3 (BC, CD, AC)
deg(D) = 3 (CD, DE, BD)
deg(E) = 2 (DE, EA)
Step 3 — Count odd-degree vertices.
Odd: A, B, C, D (4 odd vertices). E is even.
Step 4 — Apply the test.
0 odd → Eulerian circuit. 2 odd → Eulerian trail only. More than 2 odd → NEITHER.
Conclusion. 4 odd vertices ⇒ NO Eulerian circuit and NO Eulerian trail. At least one edge would have to be traversed more than once.
3. Faded example — fill in the missing steps
Network: vertices A, B, C, D with edges AB, BC, CD, DA, AC. Decide if an Eulerian circuit or trail exists. 4 marks
Step 1 — Connected? ___ (yes/no)
Step 2 — Degrees.
deg(A) = ____ deg(B) = ____ deg(C) = ____ deg(D) = ____
Step 3 — Count odd-degree vertices: ____ odd vertices.
Step 4 — Decision: Eulerian circuit / Eulerian trail / Neither — ________________
If a trail exists, start and end at the two odd vertices. Find one Eulerian trail: ______ → ______ → ______ → ______ → ______ → ______
4. Graduated practice — Eulerian tests and traversals
Foundation — single-step facts (4 questions)
| Q | Problem | Answer |
|---|---|---|
| 4.1 1 | Does a square ABCD (edges AB, BC, CD, DA) have an Eulerian circuit? | |
| 4.2 1 | Does the path A–B–C–D–E have an Eulerian circuit or trail? | |
| 4.3 1 | How many odd-degree vertices does the complete graph K₄ have? | |
| 4.4 1 | True or false: every Eulerian circuit is also an Eulerian trail. |
Standard — typical HSC difficulty (6 questions)
4.5 A network has degree sequence 2, 2, 2, 2 (a 4-cycle). Does it have an Eulerian circuit? Justify in one sentence. 2 marks
4.6 A network has degree sequence 2, 3, 3, 4, 4. (a) Does it have an Eulerian circuit? (b) Does it have an Eulerian trail? 2 marks
4.7 Network with edges AB, BC, CA (a triangle). State whether an Eulerian circuit exists and give the circuit if so. 2 marks
4.8 Network with edges AB, BC, CD (a 3-edge path). Find the Eulerian trail and state its start and end vertices. 2 marks
4.9 A network has vertices with degrees 3, 3, 4, 4, 4. (a) Is it possible? Use the handshaking lemma. (b) If yes, does it have an Eulerian circuit or trail? 2 marks
4.10 A network has 4 vertices, each of degree 3 (this is K₄). Is an Eulerian circuit or trail possible? Explain. 2 marks
Extension — find a traversal (2 questions)
4.11 Pentagon ABCDE with one diagonal AC. (a) Compute the degree of each vertex. (b) Decide whether an Eulerian circuit or trail exists. (c) If yes, find one (writing the route in full). 3 marks
4.12 A street-cleaning truck must drive every street in a small grid. The network has edges: PQ, PR, QR, QS, RS, RT, ST. (a) Compute degrees. (b) Decide whether an Eulerian circuit or trail exists. (c) If a trail exists, give a starting and ending vertex. 3 marks
5. Self-check the easy 3
Tick the first three once you've checked your method works.
How did this worksheet feel?
What I'll revisit before next class:
Q1.1 — Conditions
Eulerian circuit: connected AND every vertex has even degree. Eulerian trail: connected AND exactly 2 vertices have odd degree.
Q1.2 — Start and end of an Eulerian trail
You must start at one odd-degree vertex and end at the other odd-degree vertex.
Q1.3 — Königsberg
Each of the 4 vertices had degree 3. With 4 odd-degree vertices, neither an Eulerian circuit nor an Eulerian trail exists.
Q3 — Faded example (square ABCD with diagonal AC)
Step 1: Connected — yes.
Step 2: deg(A) = 3, deg(B) = 2, deg(C) = 3, deg(D) = 2.
Step 3: Odd vertices: 2 (A and C).
Step 4: Eulerian trail (exactly 2 odd ⇒ trail, not circuit).
Trail: A–B–C–D–A–C (uses AB, BC, CD, DA, AC). Starts at A, ends at C.
Q4.1 — Square ABCD
Yes — every vertex has degree 2 (even), and the network is connected. Eulerian circuit: A–B–C–D–A.
Q4.2 — Path A–B–C–D–E
Degrees: 1, 2, 2, 2, 1. Two odd vertices (A and E) ⇒ Eulerian trail only (not a circuit). Trail: A–B–C–D–E.
Q4.3 — Odd-degree vertices of K₄
Every vertex of K₄ has degree 3 (odd). All 4 vertices are odd.
Q4.4 — Every Eulerian circuit is also an Eulerian trail?
True. A circuit is a closed trail (no repeated edges) that uses every edge. Treated as an "open" walk it satisfies the trail requirements (no repeated edges) — it just happens to be closed.
Q4.5 — Degree sequence 2, 2, 2, 2
All degrees even ⇒ Eulerian circuit exists (assuming connected — for a 4-cycle, yes).
Q4.6 — Degree sequence 2, 3, 3, 4, 4
Odd vertices: two (the two 3s). (a) No circuit (not all even). (b) Yes, Eulerian trail; start at one degree-3 vertex, end at the other.
Q4.7 — Triangle ABC
All degrees = 2 (even), connected ⇒ Eulerian circuit exists: A–B–C–A.
Q4.8 — Path AB, BC, CD
Degrees: A = 1, B = 2, C = 2, D = 1. Two odd ⇒ trail. Eulerian trail: A–B–C–D, starts at A, ends at D (or D → A in reverse).
Q4.9 — Degree sequence 3, 3, 4, 4, 4
(a) Sum = 3+3+4+4+4 = 18 (even). Possible (9 edges by handshaking). (b) 2 odd ⇒ Eulerian trail (no circuit because not all even).
Q4.10 — K₄ (each vertex degree 3)
4 odd-degree vertices ⇒ neither an Eulerian circuit nor trail exists. (To traverse every edge once we would need 0 or 2 odd vertices.)
Q4.11 — Pentagon ABCDE + diagonal AC
(a) Edges: AB, BC, CD, DE, EA, AC. Degrees: deg(A) = 3 (AB, EA, AC); deg(B) = 2 (AB, BC); deg(C) = 3 (BC, CD, AC); deg(D) = 2 (CD, DE); deg(E) = 2 (DE, EA).
(b) Two odd vertices (A and C) ⇒ Eulerian trail exists (no circuit).
(c) Trail starting at A ending at C: A–B–C–D–E–A–C. Edges used: AB, BC, CD, DE, EA, AC ✓ (all 6 edges, none repeated).
Q4.12 — Edges PQ, PR, QR, QS, RS, RT, ST
(a) deg(P) = 2 (PQ, PR); deg(Q) = 3 (PQ, QR, QS); deg(R) = 4 (PR, QR, RS, RT); deg(S) = 3 (QS, RS, ST); deg(T) = 2 (RT, ST). Sum = 14 = 2 × 7 ✓.
(b) Two odd vertices (Q and S) ⇒ Eulerian trail.
(c) Start at Q, end at S (or vice versa). One valid trail: Q–P–R–Q–S–R–T–S.