Lesson 5: Walks, trails, paths, circuits and cycles
Finding the bridges in a road network
SkillWalks, trails, paths and cycles
Worked example
The graph shows the roads between eight towns, to .
(a) Is the graph connected?
(b) Identify every bridge.
(c) Road is closed for repairs. Can every town still be reached from every other town? Explain.
Step 1: Check whether the graph is connected
From you can reach and , then along , and from the towns , , and . Every town can be reached, so the graph is connected.
Step 2: Use cycles to rule edges out
An edge that lies on a cycle is never a bridge, because the rest of the cycle still links its two ends.
If edge is on a cycle, going the long way round the cycle still gets you from to .
Step 3: Rule out the edges on cycles
, and lie on the cycle –––. , , and lie on the cycle ––––. None of these is a bridge.
Step 4: Test the edges that are left
Removing separates , and from the other towns. Removing cuts off . So the bridges are and .
Step 5: Answer part (c)
lies on the cycle ––––, so it is not a bridge. Traffic can detour –––, and every town can still be reached.
Answer
(a) Yes, the graph is connected. (b) and . (c) Yes: is not a bridge, because it lies on the cycle ––––, so ––– is a detour.
Try a similar one
A fresh question of the same kind, checked as you answer, with hints and a full solution.
Method
Edges that lie on a cycle are not bridges.
For each remaining edge ask: if it were removed, could its two ends still reach each other?
Watch out for
Overlooking an edge to a vertex of degree 1. Removing it isolates that vertex, so it is a bridge.