Mathematics Standard • Year 12 • Module 5 • Lesson 1

Introduction to Networks — Skill Drill

Build fluency in the core network basics: identifying vertices and edges, calculating the degree of each vertex, and applying the handshaking lemma.

Build · Skill Drill

1. Quick recall

Answer each question in the space provided. 1 mark each

Q1.1 Complete each definition:

A vertex is __________________________________.

An edge is _____________________________________.

A weighted network is one where ______________.

Q1.2 Write the handshaking lemma as an equation:

Sum of all degrees = ____ × (number of __________).

Q1.3 A network has 4 vertices A, B, C, D. List the edges of the complete graph on these 4 vertices (every vertex joined to every other).

Stuck? Revisit lesson § Key Ideas — handshaking lemma and degree.

2. Worked example — degrees and the handshaking lemma

Follow each line. Every step has a reason on the right.

Problem. Four friends — Ali, Ben, Chloe, Dana — compare who knows whom. Ali knows Ben and Chloe. Ben knows Ali, Chloe and Dana. Chloe knows Ali, Ben and Dana. Dana knows Ben and Chloe. (a) Draw the network. (b) Find each vertex's degree. (c) Verify the handshaking lemma.

Step 1 — List the edges (one per pair).

Edges: AB, AC, BC, BD, CD (5 edges in total)

Reason: each friendship is one edge; AB and BA are the same.

Step 2 — Count edges at each vertex (its degree).

deg(A) = 2 (AB, AC)
deg(B) = 3 (AB, BC, BD)
deg(C) = 3 (AC, BC, CD)
deg(D) = 2 (BD, CD)

Reason: degree = number of edges meeting that vertex.

Step 3 — Sum the degrees.

Sum = 2 + 3 + 3 + 2 = 10

Step 4 — Check the handshaking lemma.

2 × (number of edges) = 2 × 5 = 10 ✓

Reason: each edge contributes 1 to the degree at each end, so it is counted twice in the sum.

Conclusion. Degrees (2, 3, 3, 2); sum = 10 = 2 × 5 edges. Handshaking lemma confirmed.

3. Faded example — fill in the missing steps

A network has vertices P, Q, R, S, T with edges PQ, PR, QR, QS, RS, RT, ST. Fill in each blank. 4 marks

Step 1 — Number of edges. Count: ____ edges.

Step 2 — Degree of each vertex.

deg(P) = ____ deg(Q) = ____ deg(R) = ____ deg(S) = ____ deg(T) = ____

Step 3 — Sum of degrees: Sum = _____ + _____ + _____ + _____ + _____ = ____

Step 4 — Handshaking check: 2 × (edges) = 2 × ____ = ____ Match the sum? ____ (yes/no)

Conclusion. All degrees confirmed by lemma: ____ (yes/no).

Stuck? Revisit lesson § Worked Example — degrees and handshaking.

4. Graduated practice — networks, degrees and matrices

Show your working in the space below each part.

Foundation — single-step facts (4 questions)

Q	Problem	Answer
4.1 1	A network has 8 edges. What is the sum of all the degrees?
4.2 1	A network has degree sequence 2, 2, 3, 3, 4. How many edges does it have?
4.3 1	State whether 1, 2, 3, 4 can be the degree sequence of a network. (Yes / No only.)
4.4 1	What does a "1" in row B, column C of an adjacency matrix represent?

Standard — typical HSC difficulty (6 questions)

Show one line of substitution where possible, and label your answer.

4.5 Draw a network with vertices A, B, C, D, E and edges AB, AC, BD, BE, CD, DE. Find the degree of each vertex. 2 marks

4.6 A network has 6 vertices, each of degree 3. Use the handshaking lemma to find the number of edges. 2 marks

4.7 Five towns A, B, C, D, E are connected by roads. The road distances are: A–B = 9 km, A–C = 12 km, B–C = 6 km, B–D = 8 km, C–E = 7 km, D–E = 5 km. Draw the weighted network and find the degree of vertex C. 2 marks

4.8 Write the adjacency matrix for the network in Q4.5 (using 1 for connected and 0 for not connected). 2 marks

4.9 Explain in one sentence why the degree sequence 1, 2, 3, 3, 4 is impossible for any network. 2 marks

4.10 A network has 7 vertices and 10 edges. Find the average degree of a vertex. 2 marks

Extension — combine ideas (2 questions)

4.11 A social network at a Sydney workplace has 8 employees. Every employee is connected (knows) exactly 3 others. (a) Use the handshaking lemma to find the number of "knowing" pairs (edges). (b) Explain why an 8-person network where everyone knows exactly 5 others would also be possible, but a 7-person network where everyone knows exactly 3 others would NOT be. 3 marks

4.12 The adjacency matrix for a network with vertices A, B, C, D is shown.

	A	B	C	D
A	0	1	1	0
B	1	0	1	1
C	1	1	0	1
D	0	1	1	0

(a) List the edges. (b) Find the degree of each vertex. (c) Verify the handshaking lemma. 3 marks

Stuck on 4.12? Read the matrix row by row: every "1" represents one edge to the column vertex (and is recorded once when you list edges).

5. Self-check the easy 3

Tick the first three once you've checked your method works.

For 4.1 I multiplied edges by 2 (handshaking lemma), not the other way around.

For 4.2 I divided the sum of degrees by 2 to get the number of edges.

For 4.3 I checked the sum of degrees is even (it must be, by the lemma).

How did this worksheet feel?

Got it Partly Lost

What I'll revisit before next class:

Answers — Do not peek before attempting

Q1.1 — Definitions

Vertex: a point (node) in a network, usually representing a place, person or object. Edge: a line connecting two vertices, representing a relationship, route or connection. Weighted network: each edge has a number attached (distance, cost, time, etc.).

Q1.2 — Handshaking lemma

Sum of all degrees = 2 × (number of edges).

Q1.3 — Complete graph on A, B, C, D (K₄)

Edges: AB, AC, AD, BC, BD, CD (6 edges).

Q3 — Faded example (PQ, PR, QR, QS, RS, RT, ST)

Step 1: 7 edges.
Step 2: deg(P) = 2, deg(Q) = 3, deg(R) = 4, deg(S) = 3, deg(T) = 2.
Step 3: Sum = 2 + 3 + 4 + 3 + 2 = 14.
Step 4: 2 × 7 = 14. Match? Yes.
Conclusion: All degrees confirmed — yes.

Q4.1 — Sum of degrees, 8 edges

Sum = 2 × 8 = 16.

Q4.2 — Edges from degree sequence 2, 2, 3, 3, 4

Sum = 14. Edges = 14 ÷ 2 = 7.

Q4.3 — Is 1, 2, 3, 4 a valid degree sequence?

Sum = 1 + 2 + 3 + 4 = 10 (even). 10 ÷ 2 = 5 edges. Yes — valid in principle (any concrete network with this sequence is possible).

Q4.4 — Meaning of a "1" at (B, C) in an adjacency matrix

It means there is an edge between B and C (they are directly connected).

Q4.5 — Degrees for edges AB, AC, BD, BE, CD, DE

deg(A) = 2 (AB, AC); deg(B) = 3 (AB, BD, BE); deg(C) = 2 (AC, CD); deg(D) = 3 (BD, CD, DE); deg(E) = 2 (BE, DE). Degree sequence: 2, 3, 2, 3, 2 (sum 12 = 2 × 6 edges ✓).

Q4.6 — 6 vertices each of degree 3

Sum of degrees = 6 × 3 = 18. By the handshaking lemma, 18 = 2 × edges, so edges = 9.

Q4.7 — Weighted network, degree of C

Edges containing C: A–C (12 km), B–C (6 km), C–E (7 km). deg(C) = 3.

Q4.8 — Adjacency matrix for edges AB, AC, BD, BE, CD, DE

A B C D E
A 0 1 1 0 0
B 1 0 0 1 1
C 1 0 0 1 0
D 0 1 1 0 1
E 0 1 0 1 0

(Symmetric about the diagonal — undirected network. Total 1s = 12 = 2 × 6 edges ✓.)

Q4.9 — Why 1, 2, 3, 3, 4 is impossible

Sum = 1 + 2 + 3 + 3 + 4 = 13, which is odd. The handshaking lemma requires an even sum (always 2 × edges). So no network has this degree sequence.

Q4.10 — Average degree, 7 vertices, 10 edges

Sum of degrees = 2 × 10 = 20. Average = 20 ÷ 7 ≈ 2.86.

Q4.11 — Workplace social network

(a) Sum of degrees = 8 × 3 = 24. Edges = 24 ÷ 2 = 12 knowing pairs.
(b) 8 people × 5 = 40 (even) ⇒ 20 edges, possible. But 7 people × 3 = 21 (odd), which violates the handshaking lemma — impossible.

Q4.12 — Read the adjacency matrix

(a) Edges (each "1" appears symmetrically — list each pair once): AB, AC, BC, BD, CD (5 edges).
(b) deg(A) = 2; deg(B) = 3; deg(C) = 3; deg(D) = 2.
(c) Sum = 2 + 3 + 3 + 2 = 10. 2 × edges = 2 × 5 = 10 ✓. Handshaking lemma holds.