Testing Connectivity by Deleting an Edge
Removing a vertex and removing an edge are different tests of connectivity. A vertex deletion removes that vertex and all its incident edges; an edge deletion removes just one connection and keeps both endpoints. To decide whether an edge is essential to the connections in a graph, compare the number of connected components before and after deleting it.
All graphs in this tutorial are finite, simple, and undirected. A path is a sequence of distinct vertices in which consecutive vertices are adjacent. A graph is connected if every pair of its vertices is joined by a path. A connected component is a maximal connected subgraph; in particular, an isolated vertex is a component of its own. Write \(c(G)\) for the number of connected components of \(G\), counting isolated vertices. The graph with no vertices has \(c(G)=0\).
This definition applies whether \(G\) is connected or disconnected. An edge in one component cannot affect the other components, but it may split its own component. The component count, not just whether the whole graph remains connected, is therefore the useful quantity.
What One Edge Deletion Can Do
Proof. Let \(e=uv\), and consider the component \(C\) containing \(u\) and \(v\). Deleting \(e\) does not change any other component. If \(C\) stays connected, the total number of components does not change. If it becomes disconnected, take any vertex \(x\) of \(C\). There is a path in \(C\) from \(x\) to \(u\). If that path avoids \(e\), then \(x\) is still connected to \(u\) in \(C-e\). If it uses \(e\), its final traversal of \(e\) must be from \(v\) to \(u\), since the path ends at \(u\) and has no repeated vertices. The part of the path from \(x\) to \(v\) avoids \(e\), so \(x\) is still connected to \(v\). Thus every vertex of \(C\) belongs in \(C-e\) to the component of \(u\) or the component of \(v\). If \(C-e\) is disconnected, \(u\) and \(v\) lie in different components, so there are exactly two pieces. The component containing \(C\) has been replaced by two components, increasing the total count by one. \(\square\)
Proof. By definition, \(e\) is a bridge exactly when \(c(G-e)>c(G)\). The lemma shows that this strict increase must be exactly one, so the first two conditions are equivalent. If \(u\) and \(v\) remain connected in \(G-e\), then the component that contained them stays connected: any path that used \(e\) can replace that edge by a path between \(u\) and \(v\) in \(G-e\). No other component changes, so \(c(G-e)=c(G)\). Conversely, if \(u\) and \(v\) are disconnected in \(G-e\), the original component containing them splits into two, as shown in the lemma. Hence \(c(G-e)=c(G)+1\). This proves the equivalence. \(\square\)
The theorem gives a practical test: record \(c(G)\), delete one edge at a time, and recount the components. The edge is a bridge precisely when the count rises by one. It is not enough to check whether the graph is still connected: if the graph was already disconnected, deleting an edge might split one component while leaving the others unchanged.
Worked Edge-Deletion Tests
Worked Example: A Connected Graph with Two Bridges
Let \(G\) have vertex set \(V=\{1,2,3,4,5\}\) and edge set \(E=\{12,23,31,34,45\}\). The vertices form one connected component, so \(c(G)=1\). Test each edge by deleting it.
| Deleted edge | Components of the resulting graph | Count |
|---|---|---|
| 12 | \(\{1,2,3,4,5\}\) | 1 |
| 23 | \(\{1,2,3,4,5\}\) | 1 |
| 31 | \(\{1,2,3,4,5\}\) | 1 |
| 34 | \(\{1,2,3\},\{4,5\}\) | 2 |
| 45 | \(\{1,2,3,4\},\{5\}\) | 2 |
For edge \(12\), for example, the remaining edges \(23\) and \(31\) still connect vertices \(1,2,3\), and \(34,45\) still attach \(4,5\). Thus deleting \(12\) leaves one component. The same check works for \(23\) and \(31\): after each deletion, the other two edges among \(1,2,3\) keep those vertices connected, and \(34,45\) attach the remaining vertices. Deleting \(34\) separates \(\{1,2,3\}\) from \(\{4,5\}\); deleting \(45\) leaves vertex \(5\) isolated from \(\{1,2,3,4\}\).
Check: The starting count is \(1\). The counts after deleting \(12,23,31\) are each \(1\), while the counts after deleting \(34\) and \(45\) are each \(2=1+1\). Therefore \(34\) and \(45\), and only those edges, are bridges.
Worked Example: Testing Edges in a Disconnected Graph
Let \(G\) have vertex set \(V=\{a,b,c,d,e,f,g\}\) and edge set \(E=\{ab,bc,cd,da,be,ef\}\). The vertices \(\{a,b,c,d,e,f\}\) form one component, and \(g\) is isolated. Hence \(c(G)=2\). The four edges \(ab,bc,cd,da\) connect \(a,b,c,d\); the edges \(be,ef\) attach \(e,f\).
| Deleted edge | Components of the resulting graph | Count |
|---|---|---|
| ab | \(\{a,b,c,d,e,f\},\{g\}\) | 2 |
| bc | \(\{a,b,c,d,e,f\},\{g\}\) | 2 |
| cd | \(\{a,b,c,d,e,f\},\{g\}\) | 2 |
| da | \(\{a,b,c,d,e,f\},\{g\}\) | 2 |
| be | \(\{a,b,c,d\},\{e,f\},\{g\}\) | 3 |
| ef | \(\{a,b,c,d,e\},\{f\},\{g\}\) | 3 |
For each of the first four deletions, the remaining three edges among \(a,b,c,d\) still connect those four vertices, and \(be,ef\) still attach \(e,f\). The isolated vertex \(g\) remains a separate component, so each resulting count is \(2\). Deleting \(be\) separates \(\{e,f\}\) from \(\{a,b,c,d\}\), while \(g\) stays isolated. Deleting \(ef\) isolates \(f\); the other vertices \(\{a,b,c,d,e\}\) remain connected, and \(g\) is still isolated.
Check: The starting count is \(2\), not \(1\), because \(g\) is an isolated vertex. The deletions \(be\) and \(ef\) each give \(3=2+1\) components, so both are bridges. Each other deletion leaves the count at \(2\), so none of \(ab,bc,cd,da\) is a bridge.
Worked Example: A Multiple-Route Section and a Tail
Let \(G\) have vertex set \(V=\{1,2,3,4,5,6\}\) and edge set \(E=\{12,13,23,24,34,45,56\}\). The graph is connected, so \(c(G)=1\). Test all seven edges.
| Deleted edge | Why the remaining graph is connected, or its components | Count |
|---|---|---|
| 12 | \(1\) reaches \(2\) by \(1,3,2\) | 1 |
| 13 | \(1\) reaches \(3\) by \(1,2,3\) | 1 |
| 23 | \(2\) reaches \(3\) by \(2,1,3\) | 1 |
| 24 | \(2\) reaches \(4\) by \(2,3,4\) | 1 |
| 34 | \(3\) reaches \(4\) by \(3,2,4\) | 1 |
| 45 | \(\{1,2,3,4\},\{5,6\}\) | 2 |
| 56 | \(\{1,2,3,4,5\},\{6\}\) | 2 |
For the first five deletions, the displayed remaining path connects the endpoints of the deleted edge. The rest of the graph still attaches to those vertices through the listed edges, including the tail \(45,56\); therefore the whole graph remains connected. Deleting \(45\) leaves the vertices \(\{1,2,3,4\}\) connected and leaves \(\{5,6\}\) connected by \(56\), with no edge between the two sets. Deleting \(56\) leaves \(6\) isolated and the other five vertices connected.
Check: The initial count is \(1\). The first five deletions each give count \(1\); the last two each give count \(2=1+1\). Thus the bridges are \(45\) and \(56\).
Common Mistakes and Why the Test Matters
Forgetting isolated vertices changes the answer. In the second example, a mistaken starting count of \(1\) would ignore \(g\). Deleting \(be\) actually produces three components, \(\{a,b,c,d\}\), \(\{e,f\}\), and \(\{g\}\), rather than two. Comparing that incorrect count with the incorrect starting count could conceal the fact that the component count has increased. Always count every isolated vertex both before and after deletion.
Do not assume every deletion increases the count. The edge \(12\) in the first example can be removed without changing the count: the other edges still connect its endpoints. The theorem says an edge deletion either leaves the count unchanged or increases it by exactly one; it does not say that every edge is a bridge.
Do not confuse edge deletion with vertex deletion. In \(G-e\), both endpoints remain in the graph. If deleting an edge leaves one endpoint with no incident edges, that endpoint still counts as a vertex and may form an isolated component. A vertex-deletion test removes the vertex itself as well, so its component count answers a different question.
Edge-deletion tests are useful when an edge list is available and the graph is small enough to inspect directly. For each edge, the relevant question is local to its original component: does that component remain connected, or does it split into two? The rest of the graph supplies an unchanged baseline to the count.
Check Your Understanding
For each question, count isolated vertices as components and compare the component counts before and after deletion.
- Let \(V=\{1,2,3,4\}\) and \(E=\{12,23,34\}\). Find \(c(G)\), then test each edge for being a bridge.
- Let \(V=\{a,b,c,d,e\}\) and \(E=\{ab,bc,ca,de\}\). What is \(c(G)\), and which edges are bridges?
- Prove that if the endpoints of an edge remain connected after its deletion, the graph’s component count is unchanged.
- Can deleting one edge increase the component count by two? Explain using the lemma.
- In a disconnected graph, why is checking only whether \(G-e\) is connected not a sufficient bridge test?