The idea, step by step
The connections define the network
A network is connected when every pair of vertices can be joined by a route. A component is a largest connected piece. Moving vertices on the page does not change their connections. Crossing lines are joined only when the crossing is explicitly marked as a vertex.
For an undirected network without loops, a vertex degree counts the incident edges. Adding all degrees counts each edge twice because it has two endpoints. The degree sum should therefore be twice the edge count.
State repetition rules
A walk can repeat edges and vertices. Here a path has no repeated vertices, and a cycle returns to its starting vertex without repeating any other vertex. Some texts use different conventions, so state what repetition is permitted in a route problem.
A bridge is an edge whose removal disconnects a connected network. Bridges matter for reliability: a broken bridge edge has no alternative connection. A network can contain a cycle in one region and bridges in another.
A common trap
Two drawn lines cross, so the crossing must be a vertex.
Instead: Only explicitly marked vertices join connections.
See the thinking
Degrees and bridges
Find the degree of C and identify bridges in the shown network.
- C connects to A, B and D, giving degree 3.
- Removing C–D separates the triangle from D and E.
- Removing D–E isolates E.
Check the edge count
A loop-free undirected network has degrees 3, 3, 2 and 2. How many edges are there?
- The degree sum is .
- Each edge contributes two ends.
Check your understanding
Removing one edge splits a connected network into two components. What is that edge called?
Show answer
A bridge.
Its removal destroys connectedness.
Your turn
6 questions · 12 marks · Work at your own pace.
Read the questions online
- Edges are AB, AC, BC and CD. Find the degrees of A, B, C and D.2 marks
- For AB, AC, BC and CD, name a cycle.2 marks
- For AB, AC, BC and CD, identify a bridge.2 marks
- An undirected loop-free network has degrees 1, 2, 2 and 1. Find the edge count.2 marks
- Edges are AB, BC and DE. How many components are present?2 marks
- Can A–B–C–B–D be a path when paths may not repeat vertices?2 marks
Read the worked solutions
Equivalent correct methods earn the corresponding marks. Include units where asked.
- Edges are AB, AC, BC and CD. Find the degrees of A, B, C and D.2 marks
Count incident edges at each vertex.
The sum 8 is twice the 4 edges.
2, 2, 3, 1. - For AB, AC, BC and CD, name a cycle.2 marks
All three edges exist.
The route closes without repeating an internal vertex.
A–B–C–A. - For AB, AC, BC and CD, identify a bridge.2 marks
D has no other connection.
Removing it isolates D.
C–D. - An undirected loop-free network has degrees 1, 2, 2 and 1. Find the edge count.2 marks
The degree sum is 6.
.
3. - Edges are AB, BC and DE. How many components are present?2 marks
A, B and C form one component.
D and E form the other.
2. - Can A–B–C–B–D be a path when paths may not repeat vertices?2 marks
B appears twice.
That violates the stated path rule.
No; it can be a walk if all edges exist.
Curriculum reference & lesson scope
SACE Board of South Australia
Stage 1 General Mathematics: matrices and networks. Original learning resources follow the approved Ascent Library chapter map.
Official curriculum source ↗