Mathematics Standard • Year 12 • Module 5 • Lesson 1
Introduction to Networks — Past-Paper Style
Practise HSC Mathematics Standard 2 short-answer and extended-response writing on networks — degree, handshaking, and adjacency matrices.
1. Short-answer questions
1.1 A network has 10 edges. Use the handshaking lemma to find the sum of the degrees of all the vertices, and hence find the average degree if the network has 8 vertices. 3 marks Band 3
1.2 The diagram represents friendships between six members of a Sydney study group. Their adjacency table is:
A → B, C, D B → A, C C → A, B, D, E
D → A, C, F E → C, F F → D, E
(a) Find the degree of each vertex.
(b) Verify the handshaking lemma.
(c) State which student has the highest degree. 3 marks Band 3-4
1.3 The adjacency matrix below represents a road network linking five suburbs of Newcastle.
| P | Q | R | S | T | |
|---|---|---|---|---|---|
| P | 0 | 1 | 0 | 1 | 1 |
| Q | 1 | 0 | 1 | 0 | 1 |
| R | 0 | 1 | 0 | 1 | 1 |
| S | 1 | 0 | 1 | 0 | 1 |
| T | 1 | 1 | 1 | 1 | 0 |
(a) List the edges of the network.
(b) Find the total number of edges and verify your answer using the handshaking lemma.
(c) The council closes the road between P and T for resurfacing. Find the new degree of T. 4 marks Band 4
2. Extended response
2.1 A small regional airline is planning routes between six rural NSW towns: Armidale (A), Bourke (B), Cobar (C), Dubbo (D), Eden (E) and Forbes (F). The proposed network is:
Direct flights will connect: A–B, A–C, A–D, B–C, B–D, C–D, C–F, D–E, D–F, E–F.
(a) Draw the network and state the number of vertices and number of edges.
(b) Find the degree of each town and verify the handshaking lemma.
(c) The airline can only afford to remove ONE route to cut costs. The marketing team wants to keep every town directly connected to Dubbo (the maintenance hub). Identify all routes that could be removed without breaking any town's direct connection to Dubbo, and write a short conclusion identifying the safest single route to remove and why. 7 marks Band 5-6
Explicit marking criteria
Part (a) — 2 marks
• 1 mark — correct diagram with all 6 vertices and 10 edges.
• 1 mark — correctly states 6 vertices and 10 edges.
Part (b) — 2 marks
• 1 mark — all six degrees correct.
• 1 mark — sum of degrees correctly equated to 2 × 10 = 20.
Part (c) — 3 marks
• 1 mark — identifies that any route NOT including D (Dubbo) preserves the "direct to Dubbo" requirement.
• 1 mark — lists all such routes accurately.
• 1 mark — explicit conclusion sentence naming the chosen route and the reason.
Your response:
Stuck on (c)? "Direct connection to Dubbo" means each town must still have at least one edge to D. Removing an edge that does not touch D cannot break that requirement.How did this worksheet feel?
What I'll revisit before next class:
1.1 — Sum and average degree (3 marks)
Sample response.
By the handshaking lemma, sum of degrees = 2 × edges = 2 × 10 = 20.
Average degree = total degrees ÷ number of vertices = 20 ÷ 8 = 2.5.
Marking notes. 1 mark — quotes the handshaking lemma (sum = 2 × edges). 1 mark — correct sum (20). 1 mark — correct average (2.5). An answer of "20 ÷ 8 = 2.5" with no statement of the lemma still scores 2/3.
1.2 — Degrees from an adjacency table (3 marks)
Sample response.
(a) deg(A) = 3, deg(B) = 2, deg(C) = 4, deg(D) = 3, deg(E) = 2, deg(F) = 2.
(b) Sum = 3+2+4+3+2+2 = 16. Edges (each pair once) = AB, AC, AD, BC, CD, CE, DF, EF = 8. 2 × 8 = 16 ✓. Handshaking lemma holds.
(c) C has the highest degree (4).
Marking notes. 1 mark — all six degrees correct. 1 mark — sum equated to 2 × edges with correct edge count. 1 mark — identifies C correctly with explicit "highest degree" justification.
1.3 — Newcastle road network (4 marks)
Sample response.
(a) Edges: P–Q, P–S, P–T, Q–R, Q–T, R–S, R–T, S–T. (8 edges.)
(b) Sum of row totals = 3+3+3+3+4 = 16. 2 × edges = 16 ⇒ edges = 8 ✓.
(c) Removing P–T drops T's degree from 4 to 3.
Marking notes. (a) 1 mark — all 8 edges listed. (b) 1 mark — edges total 8; 1 mark — handshaking verification shown. (c) 1 mark — new degree of T = 3. Common error: double-counting edges when reading the matrix (listing both PQ and QP as separate edges).
2.1 — Regional airline (7 marks): sample Band-6 response with annotations
Sample Band-6 response.
(a) Diagram and counts.
6 vertices (A, B, C, D, E, F) and 10 edges as listed: A–B, A–C, A–D, B–C, B–D, C–D, C–F, D–E, D–F, E–F. [1 mark — diagram with all vertices and edges; 1 mark — states 6 vertices and 10 edges.]
(b) Degrees and handshaking check.
deg(A) = 3 (A–B, A–C, A–D); deg(B) = 3 (A–B, B–C, B–D); deg(C) = 4 (A–C, B–C, C–D, C–F); deg(D) = 5 (A–D, B–D, C–D, D–E, D–F); deg(E) = 2 (D–E, E–F); deg(F) = 3 (C–F, D–F, E–F). [1 mark — degrees correct.]
Sum = 3+3+4+5+2+3 = 20 = 2 × 10 = 2 × (edges) ✓. [1 mark — handshaking verified.]
(c) Which route to remove?
Every town must keep at least one direct edge to D. The current D-edges are A–D, B–D, C–D, D–E, D–F. Removing any of these five would break a town's direct connection to D. Therefore the routes that can safely be removed are the five edges that do not touch D: A–B, A–C, B–C, C–F, E–F. [1 mark — recognises rule "any non-D edge"; 1 mark — lists all five such edges accurately.]
Conclusion: removing route E–F is the safest single closure, because E currently has the lowest degree (2). After removing E–F, E still has its direct flight to D, and no other town's connectivity is affected. [1 mark — explicit conclusion sentence naming a single route with reasoning.]
Total: 7/7.
Band descriptors for marker.
Band 3: Draws the network and counts edges, but degrees are partially incorrect or handshaking is not shown. ≈ 3 marks.
Band 4: Diagram, edge count and all degrees correct; handshaking verified; part (c) attempts the question but lists routes that include D, or fails to write a conclusion sentence. ≈ 4-5 marks.
Band 5: Complete (a), (b) and all five non-D routes identified in (c), but conclusion is missing or just bare list. ≈ 6 marks.
Band 6: Complete, with explicit conclusion sentence that names a single route AND justifies it (lowest-degree vertex, no further breakage). 7/7.