Mathematics Standard • Year 12 • Module 5 • Lesson 1
Introduction to Networks — Problem Set
Apply the network basics to realistic Australian scenarios: roads, computer networks, sports fixtures and friendship maps.
Problem 1 — Five towns of the NSW Riverina
Five towns A, B, C, D, E along the Murrumbidgee are connected by sealed roads with the following distances: A–B = 14 km, A–C = 22 km, B–C = 8 km, B–D = 11 km, C–D = 9 km, C–E = 18 km, D–E = 6 km.
Set up: What are we solving for?
(i) Draw the weighted network with the towns as vertices and the roads (with their distances) as edges. 2 marks
(ii) Find the degree of each town and state which town is the most "connected" (has the highest degree). 2 marks
(iii) Verify the handshaking lemma for your network. 1 mark
Stuck? Revisit lesson § Card 02 — Degree of a Vertex.Problem 2 — School computer lab
A small Sydney high school's network office connects 6 computers (C1–C6). The adjacency matrix below shows which pairs are directly connected by cable.
| C1 | C2 | C3 | C4 | C5 | C6 | |
|---|---|---|---|---|---|---|
| C1 | 0 | 1 | 1 | 0 | 0 | 1 |
| C2 | 1 | 0 | 1 | 1 | 0 | 0 |
| C3 | 1 | 1 | 0 | 1 | 1 | 0 |
| C4 | 0 | 1 | 1 | 0 | 1 | 0 |
| C5 | 0 | 0 | 1 | 1 | 0 | 1 |
| C6 | 1 | 0 | 0 | 0 | 1 | 0 |
Set up: What are we solving for?
(i) List the edges in the network (each only once). 2 marks
(ii) Find the degree of each computer. Which computer is the most heavily connected, and which is the least? 2 marks
(iii) The school IT manager wants to add ONE more cable to make C6's degree equal to C3's degree. Which new connection(s) would achieve this? List all valid choices. 2 marks
Stuck? Revisit lesson § Card 03 — Representing Networks (adjacency matrix).Problem 3 — Round-robin soccer fixture
Seven local football clubs in Wollongong are entered into a round-robin tournament. Each club plays every other club exactly once.
Set up: What are we solving for?
(i) Model the tournament as a network. State what each vertex and each edge represents. 1 mark
(ii) Use the handshaking lemma to find the number of matches that must be played. (Hint: each team plays the other 6 — so each vertex has degree 6.) 2 marks
(iii) The organisers add one more club, making 8 clubs total. By how many extra matches does the total increase? Show your full working. 2 marks
Stuck? In a complete graph (every vertex joined to every other), each vertex has degree n − 1 where n is the number of vertices.Problem 4 — Year 12 study group
In a Year 12 study group of six students — Aisha, Ben, Cam, Devi, Eli, Fatima — the friendships are: Aisha knows Ben, Cam, Devi; Ben knows Aisha, Cam; Cam knows Aisha, Ben, Devi, Eli; Devi knows Aisha, Cam, Eli, Fatima; Eli knows Cam, Devi, Fatima; Fatima knows Devi, Eli.
Set up: What are we solving for?
(i) Write the adjacency table showing each person and the people they know. 2 marks
(ii) Find the degree of each person. Verify the handshaking lemma. 2 marks
(iii) A teacher claims: "In this group, the most-connected student knows the fewest-connected student." Decide whether this claim is true or false, and justify in one sentence. 1 mark
Stuck? Revisit lesson § Worked Example — Ali, Ben, Chloe, Dana social network.Problem 5 — The impossible classroom
A teacher claims, "In my Year 12 class of 9 students, I have asked everyone to choose exactly 3 friends from within the class. Everyone has done so, and the friendships are mutual."
Set up: What are we solving for?
(i) Treat each student as a vertex and each mutual friendship as one edge. Write down the degree sequence the teacher is describing. 1 mark
(ii) Use the handshaking lemma to test whether such a network can exist. Show every line of working. 2 marks
(iii) Write a one-sentence conclusion explaining whether the teacher's claim is mathematically possible, and identify the smallest change to either (a) the number of students or (b) the number of friends each student picks that would make it possible. 2 marks
Stuck? Revisit lesson § Card 02 — the handshaking lemma forces the sum of degrees to be even.How did this worksheet feel?
What I'll revisit before next class:
Problem 1 — Five Riverina towns
Set up. We are drawing the weighted network, computing each town's degree, then verifying the handshaking lemma.
(i) Five vertices A, B, C, D, E. Edges with labels: A–B (14), A–C (22), B–C (8), B–D (11), C–D (9), C–E (18), D–E (6). Seven edges total.
(ii) deg(A) = 2 (A–B, A–C); deg(B) = 3 (A–B, B–C, B–D); deg(C) = 4 (A–C, B–C, C–D, C–E); deg(D) = 3 (B–D, C–D, D–E); deg(E) = 2 (C–E, D–E). C is the most connected town (degree 4).
(iii) Sum = 2 + 3 + 4 + 3 + 2 = 14 = 2 × 7 ✓. Handshaking lemma confirmed.
Problem 2 — School computer lab
Set up. We are reading the adjacency matrix to identify edges, compute degrees, and figure out which new edges would lift C6 to match C3.
(i) Edges (each pair once): C1–C2, C1–C3, C1–C6, C2–C3, C2–C4, C3–C4, C3–C5, C4–C5, C5–C6. 9 edges.
(ii) Row sums: deg(C1)=3, deg(C2)=3, deg(C3)=4, deg(C4)=3, deg(C5)=3, deg(C6)=2. C3 is most connected (4); C6 is least (2). Check: sum = 3+3+4+3+3+2 = 18 = 2 × 9 ✓.
(iii) We need C6's degree to rise from 2 to 4. One cable adds only 1 to deg(C6), so a single cable can lift it only to 3. To bring it to 4 we need two additional cables. Possible choices (any 2 of the 3 non-existing C6 connections): C6–C2, C6–C3, C6–C4. (Answer is acceptable if the student notes "no single cable suffices" — full marks for either spotting the impossibility OR providing the two-cable solution.)
Problem 3 — Round-robin tournament
Set up. We model the tournament as the complete graph K_n where vertices are clubs and edges are matches.
(i) Vertex = a club. Edge = one match between two clubs.
(ii) 7 clubs, each of degree 6. Sum of degrees = 7 × 6 = 42. By the lemma, matches = 42 ÷ 2 = 21 matches.
(iii) 8 clubs: each of degree 7, sum = 8 × 7 = 56, matches = 56 ÷ 2 = 28. Extra matches = 28 − 21 = 7 extra matches. (The new club plays each of the 7 existing clubs once.)
Problem 4 — Study group friendships
Set up. We are building an adjacency table from the description, computing each person's degree, then sense-checking with the handshaking lemma.
(i) Adjacency table:
Aisha → Ben, Cam, Devi
Ben → Aisha, Cam
Cam → Aisha, Ben, Devi, Eli
Devi → Aisha, Cam, Eli, Fatima
Eli → Cam, Devi, Fatima
Fatima → Devi, Eli
(ii) deg(Aisha) = 3; deg(Ben) = 2; deg(Cam) = 4; deg(Devi) = 4; deg(Eli) = 3; deg(Fatima) = 2. Sum = 3+2+4+4+3+2 = 18. Edges in the network = 9 (Aisha–Ben, Aisha–Cam, Aisha–Devi, Ben–Cam, Cam–Devi, Cam–Eli, Devi–Eli, Devi–Fatima, Eli–Fatima). 2 × 9 = 18 ✓.
(iii) Most connected = Cam or Devi (both 4). Least connected = Ben or Fatima (both 2). Cam knows Aisha, Ben, Devi, Eli — Cam DOES know Ben. So the claim is true for the pair Cam–Ben (but not for Devi–Fatima, where Devi DOES know Fatima too). A single-sentence justification can simply state: "True — Cam (highest degree 4) is directly connected to Ben (lowest degree 2)." (Marker accepts either: true with Cam–Ben evidence, or true with Devi–Fatima evidence.)
Problem 5 — The impossible classroom
Set up. We are using the handshaking lemma to test whether a degree sequence of nine 3s can exist.
(i) Degree sequence: 3, 3, 3, 3, 3, 3, 3, 3, 3 (nine 3s).
(ii) Sum of degrees = 9 × 3 = 27. By the handshaking lemma, the sum must equal 2 × edges, which is even. But 27 is odd, so no whole number of edges satisfies 2 × edges = 27. The network cannot exist.
(iii) Conclusion: the teacher's claim is mathematically impossible. Smallest fix (a): reduce the class to 8 students (8 × 3 = 24, even ⇒ 12 edges — possible). Or smallest fix (b): change "exactly 3 friends" to "exactly 2 friends" or "exactly 4 friends" (9 × 2 = 18 or 9 × 4 = 36 — both even). (Either correct fix earns the second mark.)