Connected graphs and bridges
A graph is connected when every vertex can be reached from every other vertex. A bridge is an edge whose removal increases the number of connected components
\[\text{connected}\;\Longleftrightarrow\;\text{one reachability component},\quad \text{bridge}\;\Longrightarrow\;\text{more components after removal}\]
- Test reachability Start at one vertex and follow edges to see whether every vertex can be reached \(\displaystyle \text{one component}\;\Rightarrow\;\text{connected}\)
- Remove the edge Remove a possible bridge and compare the component count before and after \(\displaystyle \#\text{components after}>\#\text{components before}\;\Rightarrow\;\text{bridge}\)
- Reject cycle edges An edge on a cycle has another route between its endpoints \(\displaystyle A\!-!B\!-!C\!-!A\;\Rightarrow\;AB\text{ is not a bridge}\)
- Check pendant edges The only edge at a degree-one vertex is a bridge \(\displaystyle \deg(A)=1,\;AB\text{ only at }A\;\Rightarrow\;AB\text{ is a bridge}\)
Worked example
A connected graph has one component. Removing AB gives 2 components, removing CD gives 2 components, and removing every other edge leaves 1 component. Find the number of bridges
\[c(G)=1,\quad c(G-AB)=2,\quad c(G-CD)=2\]
- \(\displaystyle c(G-AB)-c(G)=2-1=1\)Removing AB increases the component count, so AB is a bridge
- \(\displaystyle c(G-CD)-c(G)=2-1=1\)Removing CD also increases the component count, so CD is a bridge
- \(\displaystyle 1+1=2\)The two tested edges that increase the component count give 2 bridges
- \(\displaystyle \text{number of bridges}=2\)Every other edge leaves one component, so no further edge is a bridge
Common mistakes
Judging a bridge by appearance
✕\(\displaystyle \text{longest edge}\;\Rightarrow\;\text{bridge}\)✓\(\displaystyle \text{removal increases components}\;\Rightarrow\;\text{bridge}\)
A bridge is determined by the effect of removing the edge, not by its length or position in the drawingCalling a cycle edge a bridge
✕\(\displaystyle A\!-\!B\!-\!C\!-\!A\;\Rightarrow\;AB\text{ is a bridge}\)✓\(\displaystyle A\!-\!B\!-\!C\!-\!A\;\Rightarrow\;AB\text{ is not a bridge}\)
A cycle gives an alternative route between the endpoints, so removing one cycle edge does not disconnect the graphMissing a pendant bridge
✕\(\displaystyle \deg(A)=1\;\Rightarrow\;AB\text{ is not a bridge}\)✓\(\displaystyle \deg(A)=1\;\Rightarrow\;AB\text{ is a bridge}\)
Removing the only edge at a degree-one vertex isolates that vertex and increases the component countDifficulty levels
introDecide whether one graph is connected and give the valid reachability reason
standardSelect the disconnected graph, count bridges in a connected graph and identify a bridge edge
challengeCompare graphs with zero or two bridges and recognise a pendant bridge among cycle edges
examChoose the statement about connectivity or bridges that follows from the graph
Questions about this topic
How do you decide whether a graph is connected?+
Start at one vertex and follow all available edges. The graph is connected if every vertex can be reached from the starting vertex
Why is an edge on a cycle not a bridge?+
The other edges of the cycle provide an alternative route between the edge's endpoints, so removing that edge does not increase the number of connected components
Why is a pendant edge always a bridge?+
A pendant edge is the only edge at a degree-one vertex. Removing it leaves that vertex in a separate component
Can I use a calculator?+
No. This topic is practised without a calculator
Which year level and chapter is this?+
Year 12, VCE Units 3 & 4, General Mathematics, chapter 13: Graphs and networks
In this chapter
Count the vertices, edges and loops of a graphDegrees, the degree sum, and even and odd verticesGraph types, subgraphs, connection models and method selectionConnected graphs and bridgesIdentify isomorphic graphsPlanar graphs and drawings in planar formFaces and Euler's formulaRepresent a network in a matrixIdentify the network a connection matrix describesClassify a route: walk, trail, path, circuit or cycleEulerian trails and circuits: existence and identificationHamiltonian paths and cyclesRead a weighted graphThe shortest path by inspectionDijkstra's algorithm for shortest distances and routesTrees and spanning treesMinimum spanning trees by Prim's and Kruskal's algorithmsA full network investigation