Mathematics Standard • Year 12 • Module 5 • Lesson 2
Network Terminology — Skill Drill
Build fluency in the language of networks: complete graphs Kₙ, connected vs disconnected, trees, bipartite, and walks vs trails vs paths.
1. Quick recall
Answer each question in the space provided. 1 mark each
Q1.1 Complete the edge-counting formula for the complete graph Kₙ:
Number of edges = ____ ( ____ − ____ ) ÷ ____
Q1.2 Match each term to its definition. Write the letter beside each term.
A. No repeated edges B. No repeated vertices C. Any sequence — repeats OK
Walk = ____ Trail = ____ Path = ____
Q1.3 A tree with n vertices has exactly ____________ edges.
2. Worked example — classifying a network
Problem. A network has vertices A, B, C, D, E with edges AB, AC, BC, BD, CD, CE, DE. Decide: (a) is it connected? (b) is it complete? (c) is it a tree? (d) is it bipartite?
Step 1 — Count vertices and edges.
n = 5 vertices, edges = 7
Step 2 — Connected? Check if every vertex is reachable from A.
A → B (via AB), A → C (via AC), A → D (via AB–BD or AC–CD), A → E (via AC–CE). Yes, all reachable.
Step 3 — Complete? K₅ would need n(n−1)/2 = 5·4/2 = 10 edges. We have 7. Not complete.
Step 4 — Tree? A tree on 5 vertices has 5 − 1 = 4 edges. We have 7. Not a tree (it contains cycles).
Step 5 — Bipartite? Try a 2-colouring. Colour A red, then B and C blue (both joined to A). But B–C is an edge between two blues — fails. Not bipartite.
Conclusion. Connected: yes. Complete: no (only 7 edges, K₅ needs 10). Tree: no (more than n−1 edges, contains a cycle). Bipartite: no (contains triangle A–B–C).
3. Faded example — fill in the missing steps
Network: vertices A, B, C, D with edges AB, BC, CD, DA. Decide if it is complete, tree, bipartite. 4 marks
Step 1 — Vertices = ____, Edges = ____.
Step 2 — Complete? K₄ needs ____ × ____ ÷ 2 = ____ edges. We have ____ ⇒ Complete? ________
Step 3 — Tree? Tree on 4 vertices needs ____ edges. We have ____ ⇒ Tree? ________ (contains cycle? ________)
Step 4 — Bipartite? Try colouring A and ____ red, B and ____ blue. Every edge crosses the two colours? ________ ⇒ Bipartite? ________
Conclusion. Complete? ____, Tree? ____, Bipartite? ____.
4. Graduated practice — terminology and conversions
Foundation — single-step facts (4 questions)
| Q | Problem | Answer |
|---|---|---|
| 4.1 1 | How many edges does K₅ have? | |
| 4.2 1 | How many edges does K₆ have? | |
| 4.3 1 | A tree has 9 vertices. How many edges? | |
| 4.4 1 | Classify A–B–C–B–D in network ABCD (edges AB, BC, BD) — walk, trail, or path? |
Standard — typical HSC difficulty (6 questions)
4.5 Verify that K₄ has 6 edges using the formula n(n−1)/2. 2 marks
4.6 A network has 4 vertices and 3 edges. (a) Can it be connected? (b) If yes, must it be a tree? Explain. 2 marks
4.7 Network with edges AB, BC, CD, DA and one diagonal AC. List one walk, one trail (not a path), and one path from A to D. 2 marks
4.8 Convert the adjacency table {A→B, C; B→A, C, D; C→A, B, D; D→B, C} into an adjacency matrix using 1/0 entries. 2 marks
4.9 A bipartite network has 4 vertices in one group and 3 in the other. What is the maximum number of edges possible? 2 marks
4.10 Classify the network with edges AB, BC, CD, DE (a path on 5 vertices): is it (a) connected? (b) complete? (c) a tree? Justify each in one sentence. 2 marks
Extension — combine ideas (2 questions)
4.11 Consider a sports tournament where 6 teams play in a round-robin (every team plays every other team exactly once). (a) Model this as a complete graph Kₙ — state n. (b) Calculate the number of games using n(n−1)/2. (c) The tournament adds a seventh team. How many extra games are added? 3 marks
4.12 A network of 6 students and 4 part-time job sites at a shopping centre: students are S₁…S₆ and job sites are J₁…J₄. Each student is willing to work at each job site. (a) Is the network bipartite? Justify. (b) Draw the network with student vertices on the left and job vertices on the right (just sketch a 6×4 fully-crossed grid pattern). (c) State the number of edges. 3 marks
5. Self-check the easy 3
Tick the first three once you've checked your method works.
How did this worksheet feel?
What I'll revisit before next class:
Q1.1 — Edge formula for Kₙ
Number of edges = n(n − 1) ÷ 2.
Q1.2 — Walk / trail / path
Walk = C (any sequence). Trail = A (no repeated edges). Path = B (no repeated vertices).
Q1.3 — Tree edge count
A tree with n vertices has exactly n − 1 edges.
Q3 — Faded example (square ABCD, edges AB, BC, CD, DA)
Step 1: Vertices = 4, edges = 4.
Step 2: K₄ needs 4 × 3 ÷ 2 = 6 edges. We have 4 ⇒ Complete? No.
Step 3: Tree on 4 vertices needs 3 edges. We have 4 ⇒ Tree? No (contains cycle A–B–C–D–A: yes).
Step 4: A and C red, B and D blue. Every edge crosses (AB, BC, CD, DA all cross colours)? Yes ⇒ Bipartite? Yes.
Conclusion: Complete? No; Tree? No; Bipartite? Yes.
Q4.1 — K₅ edges
5 × 4 ÷ 2 = 10.
Q4.2 — K₆ edges
6 × 5 ÷ 2 = 15.
Q4.3 — Tree, 9 vertices
9 − 1 = 8 edges.
Q4.4 — Classify A–B–C–B–D
Edges used: AB, BC, BC (reused), BD. Edge BC repeats ⇒ NOT a trail. Vertex B repeats. So it is a walk only.
Q4.5 — Verify K₄ has 6 edges
K₄: n = 4, so edges = 4(4 − 1) ÷ 2 = 4 × 3 ÷ 2 = 6 ✓.
Q4.6 — 4 vertices, 3 edges
(a) Yes — for example A–B–C–D is a path. (b) Yes — if it is connected with exactly n − 1 = 3 edges, then by definition it is a tree (connected and acyclic).
Q4.7 — Walk / trail / path in square with diagonal AC
One possible answer: Walk A–B–C–B–D (B repeats and edge BC repeats — wait, BC then CB reuses edge BC; so walk only). Better walk: A–B–C–A–C–D (edge AC repeats). Trail (not a path) A–B–C–A–D (vertex A repeats, but no edge repeats: AB, BC, CA, AD all distinct). Path A–B–C–D (no repeats). Many correct answers possible — markers should accept any valid construction.
Q4.8 — Adjacency matrix for K₄ minus AD (square ABCD with diagonal AC and BD... actually edges given are AB, BC, AC, BD, CD)
From table: A↔B, A↔C, B↔C, B↔D, C↔D (5 edges). Matrix:
A B C D
A 0 1 1 0
B 1 0 1 1
C 1 1 0 1
D 0 1 1 0
Q4.9 — Maximum bipartite edges, groups 4 and 3
Maximum = 4 × 3 = 12 edges (every vertex in one group joined to every vertex in the other).
Q4.10 — Path A–B–C–D–E
(a) Connected: yes — there is a path between every pair (just travel along the chain). (b) Complete: no — K₅ needs 10 edges and this has 4. (c) Tree: yes — 5 vertices, 4 edges (n−1), connected, no cycles.
Q4.11 — Round-robin with 6 then 7 teams
(a) n = 6.
(b) Games = 6 × 5 ÷ 2 = 15.
(c) With 7: 7 × 6 ÷ 2 = 21. Extra = 21 − 15 = 6 extra games. (The new team plays each of the 6 existing teams once.)
Q4.12 — 6 students × 4 job sites
(a) Yes, bipartite — vertices fall into two disjoint groups (students vs sites), and edges only go between the two groups (never student-to-student or site-to-site).
(b) Sketch: 6 student vertices in a column, 4 job-site vertices in another column, every student connected to every job.
(c) Edges = 6 × 4 = 24.