Mathematics Standard • Year 12 • Module 5 • Lesson 12

Module Review: Networks and Paths — Skill Drill

A whole-module fluency drill: definitions, handshaking lemma, Eulerian/Hamiltonian checks, trees, MST (Kruskal's / Prim's), Dijkstra's, and max flow.

Build · Skill Drill

1. Quick recall — module definitions

Answer each question in the space provided. 1 mark each

Q1.1 Complete: a tree on n vertices is connected, acyclic and has exactly ____ edges.

Q1.2 Eulerian circuit exists iff ____________________; Eulerian trail exists iff ____________________.

Q1.3 The complete graph on 6 vertices K₆ has ____ edges.

Stuck? Revisit lesson 12 § Module 5 Summary.

2. Worked example — apply each concept in turn

Follow every line. The same small network is used three different ways.

Problem. Network on A, B, C, D, E with undirected edges AB = 5, AC = 3, BC = 2, BD = 6, CD = 4, CE = 1, DE = 7. Answer (a) MST total; (b) shortest A → E; (c) Eulerian check (list degrees and decide).

(a) MST. Sort: CE(1), BC(2), AC(3), CD(4), AB(5), BD(6), DE(7). Kruskal's: add CE, BC, AC, CD (→ {A,B,C,D,E}). Stop. MST = CE, BC, AC, CD. Total = 1 + 2 + 3 + 4 = 10.

(b) Shortest A → E. Dijkstra: A = 0. Visit A: B = 5, C = 3. Visit C (3): B = min(5, 5) = 5, D = 7, E = 4. Visit E (4). Shortest = 4, path A → C → E.

(c) Eulerian check. deg(A) = 2 (AB, AC). deg(B) = 3 (AB, BC, BD). deg(C) = 4 (AC, BC, CD, CE). deg(D) = 3 (BD, CD, DE). deg(E) = 2 (CE, DE). Odd vertices: B and D (exactly 2). Eulerian trail exists (but not a circuit). Trail must start at B or D and end at the other.

Conclusion. MST total = 10. Shortest A → E = 4. Eulerian: trail yes, circuit no.

3. Faded example — fill in the missing pieces

Network on A, B, C, D with AB = 7, AC = 2, BC = 4, BD = 6, CD = 3. 4 marks

3.1 — Degrees and handshaking lemma. deg(A) = ____, deg(B) = ____, deg(C) = ____, deg(D) = ____. Sum = ____. Edges in network = ____. Check: sum = 2 × ____ ✓.

3.2 — MST (Kruskal's). Sort: AC(__), CD(__), BC(__), BD(__), AB(__). Add ____, ____, ____. MST total = ____ + ____ + ____ = ____.

3.3 — Shortest A → D (Dijkstra). Visit A: B = ____, C = ____. Visit ____ (smallest = 2): B = min( ____ , ____ + ____ ) = ____, D = ____ + ____ = ____. Visit ____ (smallest = ____): D = min( ____ , ____ + ____ ) = ____. Shortest A → D = ____, path ____.

3.4 — Treat as directed A→B, A→C, B→C, B→D, C→D; capacities = weights. Max flow A → D. A → C → D: min(2, 3) = ____. A → B → D: min(7, 6) = ____. A → B → C → D: min(7 − ____ , 4, 3 − ____ ) = ____. Total max flow = ____.

Stuck? Treat each sub-question as completely separate.

4. Graduated practice — module mix

Each question targets one Module 5 idea. State the concept before solving.

Foundation — single-step facts (4 questions)

Q	Problem	Answer
4.1 1	A tree on 12 vertices has ____ edges.
4.2 1	K₅ has ____ edges.
4.3 1	True / False: Dijkstra's works with negative edge weights.
4.4 1	True / False: Max flow ≤ capacity of every cut.

Standard — typical HSC difficulty (6 questions)

State the concept then solve.

4.5 A connected network has 8 vertices and 12 edges. How many edges must be removed to leave a spanning tree? 2 marks

4.6 A network has degrees 4, 4, 2, 2, 2, 2, 2. Does it have an Eulerian circuit? Justify. 2 marks

4.7 Apply Kruskal's to AB = 4, AC = 2, BC = 5, BD = 1, CD = 3, CE = 6, DE = 2. State MST total. 2 marks

4.8 Apply Dijkstra's to find shortest A → E on the network in 4.7. 2 marks

4.9 Find max flow S → T for pipes S → A(4), S → B(6), A → T(7), B → T(3), A → B(2). 2 marks

4.10 A complete graph K_n has 21 edges. Find n. 2 marks

Extension — combine ideas (2 questions)

4.11 A road network on five towns has degrees 2, 2, 3, 3, 4. (a) Is an Eulerian circuit possible? (b) Is an Eulerian trail possible? Where could it start and end? 3 marks

4.12 Consider the network in 4.7. (a) State the algorithm and total for the MST. (b) State the algorithm and answer for shortest A → E. (c) Treat edges as directed left-to-right, weights = capacities, and state the max flow A → E. Make one observation comparing the three answers. 3 marks

Stuck on 4.10? K_n has n(n − 1)/2 edges; solve n(n − 1)/2 = 21.

5. Self-check the easy 3

Tick the first three once you've checked your method works.

For 4.1 a tree on n vertices has n − 1 edges (so 11).

For 4.3 the answer is False — Dijkstra's requires non-negative weights.

For 4.4 the answer is True — by the max-flow min-cut theorem.

How did this worksheet feel?

Got it Partly Lost

What I'll revisit before next class:

Answers — Do not peek before attempting

Q1.1 — Tree edges

n − 1 (so "n − 1") edges.

Q1.2 — Eulerian

Circuit iff all vertices have even degree; Trail iff exactly 0 or 2 vertices have odd degree.

Q1.3 — Edges in K₆

n(n − 1)/2 = 6 × 5 / 2 = 15.

Q3 — Faded example (5-vertex worked answer)

3.1 deg(A) = 2 (AB, AC); deg(B) = 3 (AB, BC, BD); deg(C) = 3 (AC, BC, CD); deg(D) = 2 (BD, CD). Sum = 10. Edges = 5. 10 = 2 × 5 ✓.
3.2 Sort: AC(2), CD(3), BC(4), BD(6), AB(7). Add AC(2), CD(3), BC(4) (or BD(6) if BC formed a cycle — check: after AC, CD, network = {A,C,D}; BC adds B → {A,B,C,D}). MST = AC, CD, BC. Total = 2 + 3 + 4 = 9.
3.3 Visit A: B = 7, C = 2. Visit C (2): B = min(7, 2+4) = 6, D = 2 + 3 = 5. Visit D (5): B not updated, no further targets. Visit B (6): D = min(5, 12) = 5. Shortest A → D = 5, path A → C → D.
3.4 A → C → D: min(2, 3) = 2. A → B → D: min(7, 6) = 6. A → B → C → D: min(7 − 6 = 1, 4, 3 − 2 = 1) = 1. Total max flow = 2 + 6 + 1 = 9.

Q4.1 — Tree on 12 vertices

11 edges.

Q4.2 — K₅ edges

5 × 4 / 2 = 10.

Q4.3 — Dijkstra and negative weights

False.

Q4.4 — Max flow vs cut capacity

True.

Q4.5 — Edges to remove for spanning tree

Tree on 8 vertices needs 7 edges. Network has 12. Remove 12 − 7 = 5 edges.

Q4.6 — Eulerian circuit on degrees 4, 4, 2, 2, 2, 2, 2

All degrees even, so Eulerian circuit exists (the network can be walked traversing every edge exactly once and returning to start).

Q4.7 — MST on 7-edge 5-vertex network

Sort: BD(1), AC(2), DE(2), CD(3), AB(4), BC(5), CE(6). Add BD, AC, DE, CD. MST total = 1 + 2 + 2 + 3 = 8.

Q4.8 — Shortest A → E

A = 0. Visit A: B = 4, C = 2. Visit C (2): B = min(4, 7) = 4, D = 5, E = 8. Visit B (4): D = min(5, 5) = 5. Visit D (5): E = min(8, 7) = 7. Visit E (7). Shortest = 7, path A → C → D → E (2 + 3 + 2 = 7) or A → B → D → E (4 + 1 + 2 = 7).

Q4.9 — Max flow S → T

S → A → T: min(4, 7) = 4. S → B → T: min(6, 3) = 3. S → B → A → T? Edge is A → B (one direction). S → A → B → T already? min(4 − 4 = 0, 2, 3 − 3 = 0) = 0. So total = 4 + 3 = 7. Cut {S} | {A, B, T}: S→A(4) + S→B(6) = 10. Cut {S, A, B} | {T}: A→T(7) + B→T(3) = 10. Cut {S, B} | {A, T}: S→A(4) + B→? no edge B→A. So just S→A(4) and B→T(3) = 7. ✓ min cut = 7.

Q4.10 — K_n with 21 edges

n(n − 1)/2 = 21 ⇒ n(n − 1) = 42. Test n = 7: 7 × 6 = 42 ✓. So n = 7.

Q4.11 — Eulerian on degrees 2, 2, 3, 3, 4

(a) No circuit — two odd vertices, not zero. (b) Yes — exactly 2 odd vertices means an Eulerian trail exists. It must start at one odd vertex and end at the other (the two vertices of degree 3).

Q4.12 — Mixed concepts on 7-edge network

(a) MST (Kruskal's): total = 8. (b) Shortest A → E (Dijkstra): 7. (c) Max flow A → E (inspection, directed left-to-right). Paths: A → B → D → E: min(4, 1, 2) = 1. A → C → D → E: min(2, 3, 2 − 1 = 1) = 1. A → C → E: min(2 − 1, 6) = 1. Total = 1 + 1 + 1 = 3. (Or, A → B → D → E = min(4,1,2) = 1; A → B → C → E uses BC = 5 and CE = 6; min(4 − 1, 5, 6) = 3; total 1 + 3 = 4. Recheck: starting flows fresh — A → B → D → E = 1 (BD = 1 bottleneck). A → C → E = min(2, 6) = 2. A → C → D → E = min(0, 3, 1) = 0. Total = 1 + 2 = 3.) Max flow ≈ 3. Observation: the three numbers (MST = 8, shortest path = 7, max flow = 3) all answer different questions about the same network.