Understand the idea.
The connections define the network
A connected undirected network lets every pair of vertices communicate along some route. Its components are its maximal connected pieces. Changing the drawing positions changes nothing unless connections change; crossing lines join only at an explicitly marked vertex.
The degree of a vertex counts its incident edges. In a loop-free undirected network, every edge contributes one to each endpoint’s degree. Therefore the total of all vertex degrees equals twice the number of edges.
State repetition rules
A walk may repeat vertices and edges. In this course a path repeats no vertices, while a cycle returns to its starting vertex without repeating another vertex. Check these restrictions before classifying or counting a route.
A bridge is an edge whose removal disconnects the network. An edge on a cycle has an alternative route around that cycle, so it is not a bridge. Test removal of the edge rather than relying on its position in the drawing.
See the method in action.
Degrees and bridges
Find the degree of C and identify bridges in the shown network.
Worked solution
- 1
List the neighbours of C.
C is joined to A, B and D by three incident edges.
- 2
Remove the C–D edge mentally.
The triangle containing A, B and C then has no connection to D or E, so C–D is a bridge.
- 3
Remove the D–E edge mentally.
E has no other connection, so removing D–E isolates E and makes that edge a bridge.
- 4
Check the remaining edges.
A–B, B–C and C–A lie on the triangle; each has an alternative route around it. The only bridges are C–D and D–E.
Degree of C = 3; bridges C–D and D–E.
Check the edge count
A loop-free undirected network has degrees 3, 3, 2 and 2. How many edges are there?
Worked solution
- 1
Add the degrees.
This counts all edge endpoints in the network.
- 2
Convert endpoints into edges.
Every undirected edge contributes two endpoints to the degree sum.
- 3
State the edge count.
Dividing by two removes the double count.
edges.
Try it yourself.
Check your understanding
Removing one edge splits a connected network into two components. What is that edge called?
Show answer & reasoning
A bridge.
The edge is a bridge: its removal increases the number of components from one to two, which is exactly the defining property.
Keep practising
6 worksheet questions · 12 marks
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 ↗