Mathematics Standard • Year 12 • Module 5 • Lesson 2
Network Terminology — Past-Paper Style
Practise HSC Mathematics Standard 2 short-answer and extended-response writing on network terminology — complete graphs, trees, bipartite networks, walks, trails and paths.
1. Short-answer questions
1.1 Twelve regional rugby league clubs play a round-robin tournament (every team plays every other once). Use the formula n(n − 1) ÷ 2 to calculate the total number of games. 2 marks Band 3
1.2 Consider the network with vertices A, B, C, D, E and edges AB, AC, AD, BC, BD, BE.
(a) Is the network connected? Justify.
(b) Is the network complete? Justify.
(c) Find the degree of each vertex. 3 marks Band 3-4
1.3 A youth basketball league has 9 teams. The organiser claims, "Each team plays exactly 4 other teams in a friendly round; a single network captures all the games."
(a) State the degree of each vertex in the proposed network.
(b) Use the handshaking lemma to test whether this can exist. Show full working.
(c) If the network does not exist, state the smallest change to the number of teams or the number of games per team that would make it possible. 4 marks Band 4
2. Extended response
2.1 A small farm shop owner is choosing how to label its delivery network. Six delivery destinations (D₁–D₆) are linked to two warehouses (W₁ and W₂) as follows: every destination must receive deliveries from either W₁ or W₂, but never both. The arrangement is:
W₁ services D₁, D₂, D₃, D₅.
W₂ services D₂, D₃, D₄, D₅, D₆.
Note: the owner has accidentally double-listed some destinations across both warehouses.
(a) Draw the network with the two warehouses on the left and the six destinations on the right. State whether it is bipartite, and justify.
(b) Find the degree of each vertex and verify the handshaking lemma.
(c) The owner must edit the schedule so each destination is serviced by EXACTLY ONE warehouse (whichever is more convenient). Identify the destinations currently double-listed, propose a sensible single-warehouse assignment (giving each destination to ONE of W₁ or W₂), and write a one-sentence conclusion explaining the resulting edge count and why bipartiteness is preserved. 7 marks Band 5-6
Explicit marking criteria
Part (a) — 2 marks
• 1 mark — correct bipartite layout with all 9 edges (counting duplicates as separate listings).
• 1 mark — correctly states bipartite with justification (vertices split into warehouses and destinations; no W–W or D–D edges).
Part (b) — 2 marks
• 1 mark — all 8 degrees correct.
• 1 mark — sum of degrees = 2 × edges shown explicitly.
Part (c) — 3 marks
• 1 mark — identifies the duplicated destinations (D₂, D₃, D₅).
• 1 mark — proposes a workable single-warehouse assignment with each duplicate resolved.
• 1 mark — explicit conclusion sentence with new edge count and bipartiteness statement.
Your response:
Stuck on (c)? You have 3 duplicates (D₂, D₃, D₅). For each, pick the warehouse it should be assigned to. The total destinations is 6 — the final edge count must also be 6.How did this worksheet feel?
What I'll revisit before next class:
1.1 — Round-robin, 12 clubs (2 marks)
Sample response.
Games = n(n − 1) ÷ 2 = 12 × 11 ÷ 2 = 66 games.
Marking notes. 1 mark — correct substitution into formula. 1 mark — correct numerical answer with "games" (or equivalent) units. Bare "66" with no formula shown scores 1/2.
1.2 — Classification (3 marks)
Sample response.
(a) Yes — every vertex reachable from A (A→B, A→C, A→D, then B→E). Connected.
(b) No — K₅ has 5 × 4 ÷ 2 = 10 edges; this has only 6. Not complete.
(c) deg(A) = 3 (AB, AC, AD); deg(B) = 4 (AB, BC, BD, BE); deg(C) = 2 (AC, BC); deg(D) = 2 (AD, BD); deg(E) = 1 (BE). Check: sum = 12 = 2 × 6 ✓.
Marking notes. 1 mark for each part. Part (a) needs explicit reachability statement (not just "yes"). Part (b) must compare to K₅'s edge count of 10. Part (c) needs all five degrees correct.
1.3 — 9 teams, 4 games each (4 marks)
Sample response.
(a) Each team plays 4 others → degree of each vertex = 4.
(b) Sum of degrees = 9 × 4 = 36 (even). By the handshaking lemma, number of games = 36 ÷ 2 = 18 games. The network can exist.
(c) Since the sum is even, no change is needed — the league can run exactly as the organiser described.
Marking notes. (a) 1 mark — degree = 4 stated. (b) 1 mark — sum calculation; 1 mark — correct conclusion that the network is possible because the sum is even. (c) 1 mark — explicit recognition that no change is required (or, equivalently, "any change preserving an even total works"). Common error: students sometimes assume it is impossible because the numbers look "off"; the handshaking-lemma check is the discriminator.
2.1 — Delivery network bipartite design (7 marks): sample Band-6 response
Sample Band-6 response.
(a) Draw and classify.
Network is bipartite: vertices fall into two disjoint groups — warehouses {W₁, W₂} on one side and destinations {D₁, …, D₆} on the other. Every edge listed (W₁–D₁, W₁–D₂, W₁–D₃, W₁–D₅, W₂–D₂, W₂–D₃, W₂–D₄, W₂–D₅, W₂–D₆) connects a warehouse to a destination — no W–W or D–D edges exist. 9 edges total. [1 mark — bipartite layout; 1 mark — explicit bipartite justification.]
(b) Degrees and handshaking.
deg(W₁) = 4 (D₁, D₂, D₃, D₅); deg(W₂) = 5 (D₂, D₃, D₄, D₅, D₆); deg(D₁) = 1; deg(D₂) = 2; deg(D₃) = 2; deg(D₄) = 1; deg(D₅) = 2; deg(D₆) = 1. [1 mark — degrees.]
Sum = 4 + 5 + 1 + 2 + 2 + 1 + 2 + 1 = 18 = 2 × 9 ✓. [1 mark — handshaking verified.]
(c) Resolve duplicates and re-assign.
Currently double-listed destinations (appear under both warehouses): D₂, D₃, D₅. [1 mark — identifies duplicates.]
Proposed single-warehouse assignment (one possible choice): assign D₂ → W₂, D₃ → W₁, D₅ → W₁. New schedule:
W₁ services D₁, D₃, D₅.
W₂ services D₂, D₄, D₆.
[1 mark — workable single-warehouse assignment.]
Conclusion: the new network has 6 edges (one per destination) and remains bipartite, because every edge still runs between the two groups {W₁, W₂} and {D₁, …, D₆} — no edge has been added within either group. [1 mark — explicit conclusion with edge count and bipartite statement.]
Total: 7/7.
Band descriptors for marker.
Band 3: Draws the network and counts edges; bipartiteness asserted but not justified; degrees partially correct. ≈ 3 marks.
Band 4: Diagram correct, degrees correct, handshaking shown; identifies duplicates but does not produce a workable re-assignment. ≈ 4-5 marks.
Band 5: All numerical parts complete and a workable assignment proposed, but no conclusion sentence about bipartiteness or edge count. ≈ 6 marks.
Band 6: Complete, with explicit conclusion sentence stating the new edge count AND bipartiteness preservation. 7/7.