Lesson 5: Walks, trails, paths, circuits and cycles

Finding the bridges in a road network

SkillWalks, trails, paths and cycles

Worked example

  • Complex familiar

The graph shows the roads between eight towns, AA to HH.

(a) Is the graph connected?

(b) Identify every bridge.

(c) Road DEDE is closed for repairs. Can every town still be reached from every other town? Explain.

1 of 5 steps
  1. Step 1: Check whether the graph is connected

    From AA you can reach BB and CC, then DD along CDCD, and from DD the towns EE, FF, GG and HH. Every town can be reached, so the graph is connected.

Try a similar one

A fresh question of the same kind, checked as you answer, with hints and a full solution.

Method

  1. Edges that lie on a cycle are not bridges.

  2. 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.

Save your progress with a free account