Mathematics Standard • Year 12 • Module 5 • Lesson 2
Network Terminology — Problem Set
Apply the terminology toolkit to realistic Australian contexts: handshake greetings, school timetabling, computer cabling and event ticket allocation.
Problem 1 — Handshakes at a Year 12 farewell
At a Year 12 farewell, 8 students stand in a circle and each student shakes hands with every other student exactly once.
Set up: What are we solving for?
(i) Model this as a complete graph Kₙ. State the value of n and the degree of each vertex. 1 mark
(ii) Using n(n − 1) ÷ 2, calculate the total number of handshakes. 2 marks
(iii) Two more students arrive late and also shake hands with everyone (including each other). How many extra handshakes occur? Show full working. 2 marks
Stuck? Revisit lesson § Card 01 — Complete graph Kₙ formula.Problem 2 — School timetable: students and elective subjects
A small senior school has 5 students (S₁…S₅) and 3 electives (Drama D, Music M, Photography P). Their elective choices are: S₁ → D, M; S₂ → M; S₃ → D, P; S₄ → P; S₅ → D, M, P.
Set up: What are we solving for?
(i) Explain why this network is bipartite, identifying the two groups. 1 mark
(ii) Draw the bipartite network. State the number of edges and the degree of each elective. 2 marks
(iii) A new student S₆ enrols and chooses all 3 electives. By how many does the total number of edges increase, and which elective is now the most popular? 2 marks
Stuck? Revisit lesson § Card 01 — Bipartite networks.Problem 3 — Library Wi-Fi extender layout
A school library installs 6 Wi-Fi extenders W₁…W₆ in a tree layout. The connections (cables) are: W₁–W₂, W₁–W₃, W₂–W₄, W₂–W₅, W₃–W₆.
Set up: What are we solving for?
(i) Show that this network satisfies the tree formula (n − 1 edges) and is therefore a tree. 2 marks
(ii) Find the degree of W₂. Explain in one sentence why removing W₂'s cable to W₁ would disconnect the network. 2 marks
(iii) A technician adds ONE additional cable W₅–W₆. (a) Is the new network still a tree? (b) How many cycles does it now contain? 2 marks
Stuck? Revisit lesson § Card 01 — adding any edge to a tree creates exactly one cycle.Problem 4 — Walking the school grounds
A primary school has 5 locations: Office (O), Classroom (C), Library (L), Playground (P), Sports field (S). Paths exist between: O–C, O–L, C–L, C–P, L–P, P–S.
Set up: What are we solving for?
(i) Classify each route as a walk, trail or path (use the strictest classification that applies):
(α) O–C–L–P–S
(β) O–C–L–O–L–P (note: edge OL is reused)
(γ) O–C–P–L–C (vertex C repeats but no edge repeats) 3 marks
(ii) Find all paths from Office (O) to Sports field (S). 2 marks
Stuck? Revisit lesson § Card 02 — Walks, Trails and Paths. "Strictest" means: if it has no repeated vertices, call it a path; else if no repeated edges, call it a trail; else just a walk.Problem 5 — From matrix to diagram (gold-mining haul roads)
A central NSW gold mining company has 5 work sites M₁–M₅. The adjacency matrix below shows their haul-road connections.
| M₁ | M₂ | M₃ | M₄ | M₅ | |
|---|---|---|---|---|---|
| M₁ | 0 | 1 | 1 | 0 | 0 |
| M₂ | 1 | 0 | 1 | 1 | 1 |
| M₃ | 1 | 1 | 0 | 1 | 0 |
| M₄ | 0 | 1 | 1 | 0 | 1 |
| M₅ | 0 | 1 | 0 | 1 | 0 |
Set up: What are we solving for?
(i) Sketch the network from the matrix. 2 marks
(ii) Is the network connected? Is it complete? Justify each answer briefly. 2 marks
(iii) The company plans to close one haul road. They want every site to remain reachable. Which single road(s) can they close without disconnecting the network? List them all and write a one-sentence recommendation. 3 marks
Stuck? An edge can be safely removed if and only if it lies on a cycle. Edges not on any cycle are "bridges" and removing them disconnects the network.How did this worksheet feel?
What I'll revisit before next class:
Problem 1 — Handshakes
Set up. We are using Kₙ to count handshakes (= edges) for 8 students and again for 10.
(i) n = 8; each vertex has degree n − 1 = 7.
(ii) Handshakes = 8 × 7 ÷ 2 = 28.
(iii) With 10 students: 10 × 9 ÷ 2 = 45. Extra = 45 − 28 = 17 extra handshakes.
Problem 2 — Student/elective bipartite network
Set up. We split vertices into two groups (students, electives), draw the bipartite network, count edges, then add S₆.
(i) Bipartite because vertices split into two disjoint groups — {S₁,…,S₅} (students) and {D, M, P} (electives) — and every edge goes between the two groups, never within.
(ii) Edges (student–elective pairs): S₁D, S₁M, S₂M, S₃D, S₃P, S₄P, S₅D, S₅M, S₅P. 9 edges. Degrees of electives: deg(D) = 3 (S₁, S₃, S₅); deg(M) = 3 (S₁, S₂, S₅); deg(P) = 3 (S₃, S₄, S₅).
(iii) S₆ adds 3 new edges (S₆D, S₆M, S₆P) → total now 12. After adding S₆, D, M, P each gain one student. Tie at degree 4 for all three — no single most popular elective; all three electives are equally popular (degree 4).
Problem 3 — Library Wi-Fi tree
Set up. We are checking the tree formula, examining W₂'s degree, and seeing what changes when one extra cable is added.
(i) n = 6 vertices; edges = 5 = n − 1 ✓. The network is also connected (every W is reachable from W₁). So it is a tree.
(ii) deg(W₂) = 3 (W₁, W₄, W₅). Removing the W₁–W₂ cable: W₂, W₄ and W₅ would no longer have any path back to W₁, W₃ or W₆ — the network splits into two components.
(iii) (a) No — adding any edge to a tree creates a cycle, so the new network is not a tree. (b) Exactly 1 cycle (W₅–W₂–W₁–W₃–W₆–W₅).
Problem 4 — Walks, trails and paths
Set up. We classify three given routes by the strictest rule that applies, then enumerate all paths from O to S.
(i) (α) O–C–L–P–S: no repeated vertices ⇒ path. (β) O–C–L–O–L–P: edge OL is reused (and edge LP is fine) — repeated edge ⇒ walk only. (γ) O–C–P–L–C: edges OC, CP, PL, LC are all distinct, but vertex C repeats ⇒ trail (not a path).
(ii) Paths from O to S (must end at S, which only connects via P, so all paths end "…–P–S"):
— O–C–P–S
— O–L–P–S
— O–C–L–P–S
— O–L–C–P–S
4 paths.
Problem 5 — Mining haul roads
Set up. We translate the matrix into a diagram, classify the network, then identify which edges can be removed without disconnecting it.
(i) Edges (each pair once): M₁M₂, M₁M₃, M₂M₃, M₂M₄, M₂M₅, M₃M₄, M₄M₅. 7 edges, 5 vertices.
(ii) Connected — every site reachable from M₁ (e.g., M₁→M₂→M₅, M₁→M₃→M₄). Not complete — K₅ would need 5 × 4 ÷ 2 = 10 edges; this has 7.
(iii) Cycles present include M₁–M₂–M₃–M₁, M₂–M₃–M₄–M₂, M₂–M₄–M₅–M₂. An edge can be safely removed only if it lies on a cycle. Every edge in this network is on at least one cycle (M₁M₂, M₁M₃, M₂M₃ on the first triangle; M₂M₄, M₃M₄ on the second; M₂M₅, M₄M₅ on the third). All 7 roads are removable individually without disconnecting the network. Recommendation: close one of the roads on the smallest triangle (e.g., M₁M₃) because it is part of the simplest detour, minimising routing disruption.