Why Tree Edges Are Essential
A tree is connected, so there is a route between every pair of vertices. Yet a tree has no cycle, which means its routes have no alternate way around an edge. This makes each edge essential to the connection between its endpoints: remove it, and those endpoints can no longer reach one another. The precise language for this property is that every edge of a tree is a bridge.
All graphs in this tutorial are finite and simple. 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; the number of components of \(G\) is denoted by \(c(G)\). Deleting an edge \(e\), written \(G-e\), removes that edge and keeps all vertices.
For the main result, we use the unique-path characterization of trees: in a tree, every pair of distinct vertices is joined by exactly one path. A tree is a connected acyclic graph. The characterization explains why its edges cannot have alternate routes, while the next result makes that idea precise for any graph.
Alternate Paths and Bridges
Proof. Let \(C\) be the component of \(G\) containing \(u\) and \(v\). First suppose \(G-e\) has a \(u\)-\(v\) path. We show that deleting \(e\) does not split \(C\). Take any vertex \(x\in C\). There is a path from \(x\) to \(u\) in \(G\). If that path does not use \(e\), it remains in \(G-e\), so \(x\) is still connected to \(u\). If it does use \(e=uv\), the path reaches \(v\) before using \(e\) to reach \(u\). Its portion from \(x\) to \(v\) remains after deletion, and the assumed \(u\)-\(v\) path then connects \(v\) to \(u\) in \(G-e\). Thus every vertex of \(C\) remains connected to \(u\). The other components of \(G\) are unchanged, so \(c(G-e)=c(G)\), and \(e\) is not a bridge.
Now suppose \(G-e\) has no \(u\)-\(v\) path. The vertices \(u\) and \(v\), which belonged to the same component in \(G\), lie in different components in \(G-e\). No component outside \(C\) is changed by deleting \(e\), so the component \(C\) has split and \(c(G-e)>c(G)\). Hence \(e\) is a bridge. The two implications prove the theorem. \(\square\)
This result gives a direct test: look for a route between the endpoints that avoids the edge. If one exists, the edge is not a bridge. If none exists, deleting the edge separates its endpoints and increases the component count. The route must be a path in \(G-e\); a route that uses the edge being tested is not an alternate route.
Every Edge of a Tree Is a Bridge
Proof. Assume \(e=uv\) is an edge of the tree \(T\). The edge itself is a \(u\)-\(v\) path in \(T\). Since a tree has exactly one path between any pair of distinct vertices, this edge is the unique \(u\)-\(v\) path in \(T\). If \(T-e\) still had a \(u\)-\(v\) path, that path would also be a path in \(T\), distinct from the one-edge path \(uv\). This contradicts uniqueness. Therefore \(T-e\) has no \(u\)-\(v\) path. By the bridge criterion, \(e\) is a bridge. \(\square\)
The theorem says more than that the edge has disappeared: its endpoints have become disconnected. In fact, deleting a tree edge creates exactly two components. This stronger description follows from the same unique-path idea.
Proof. The theorem shows that \(u\) and \(v\) lie in different components of \(T-e\), so there are at least two. To show there are no more, take any vertex \(x\) of \(T\). There is a unique path from \(x\) to \(u\) in \(T\). If this path avoids \(e\), it remains in \(T-e\), so \(x\) belongs to the component containing \(u\). If it uses \(e=uv\), then its portion from \(x\) to \(v\), ending just before it crosses \(e\), avoids \(e\). Thus \(x\) belongs to the component containing \(v\). Every vertex therefore lies in one of those two components, proving there are exactly two. \(\square\)
If \(T\) has a single vertex, it has no edges, so the statement about every tree edge is vacuously true. The corollary also has no edge to consider in that case. For any tree with at least one edge, the proof above applies to each edge individually.
Worked Examples
Worked Example: Removing an Edge from a Path
Let \(T=(V,E)\) be the graph with vertex set \(V=\{1,2,3,4,5\}\) and edge set \(E=\{12,23,34,45\}\). This is a path. Remove \(e=23\). The remaining edge set is \(E(T-e)=\{12,34,45\}\), and the vertex set stays \(\{1,2,3,4,5\}\).
Starting at vertex \(1\), the remaining edge \(12\) reaches \(2\), and there is no remaining edge from \(\{1,2\}\) to any of \(\{3,4,5\}\). These vertices form one component. Starting at \(3\), the edges \(34\) and \(45\) reach \(4\) and \(5\), giving the other component. Thus the components have vertex sets \(\{1,2\}\) and \(\{3,4,5\}\). In particular, \(2\) and \(3\) are disconnected.
Check: Before deletion, \(2\) and \(3\) were joined by the edge \(23\), which is their unique path in the tree. After deletion, the listed remaining edges connect the vertices within each of the two displayed sets and none connects the sets. The edge is therefore a bridge, though neither endpoint becomes isolated.
Worked Example: Removing a Branch from a Star
Let \(T=(V,E)\) have vertex set \(V=\{c,1,2,3,4\}\) and edge set \(E=\{c1,c2,c3,c4\}\). This is a star with center \(c\). Remove the edge \(c3\). The remaining edge set is \(E(T-c3)=\{c1,c2,c4\}\).
The remaining edges connect \(c\) to \(1\), \(2\), and \(4\), so \(\{c,1,2,4\}\) is connected. Vertex \(3\) has no remaining incident edge and forms the other component by itself. Consequently, the components have vertex sets \(\{c,1,2,4\}\) and \(\{3\}\); the endpoints \(c\) and \(3\) are disconnected.
Check: In the original tree, the only path from \(c\) to \(3\) was the edge \(c3\). The deletion removes that path, and the remaining edge list contains no route from \(c\) to \(3\), as the bridge criterion predicts.
Worked Example: A Cycle Edge Is Not a Bridge
To see why the tree hypothesis matters, let \(G=(V,E)\) have vertex set \(V=\{1,2,3,4\}\) and edge set \(E=\{12,23,31,34\}\). The vertices \(1,2,3\) form a triangle, and vertex \(4\) is attached by edge \(34\).
First test edge \(12\). After deleting it, the edge set is \(\{23,31,34\}\). There is still a path from \(1\) to \(2\), namely \(1,3,2\), using edges \(31\) and \(23\). The remaining edges connect all four vertices, so deleting \(12\) does not increase the number of components. The edge \(12\) is not a bridge.
Now test edge \(34\). After deleting it, the edge set is \(\{12,23,31\}\). These edges connect \(\{1,2,3\}\), while vertex \(4\) has no remaining incident edge. The components are therefore \(\{1,2,3\}\) and \(\{4\}\), so \(34\) is a bridge.
Check: The edge \(12\) lies on the cycle \(1,2,3,1\), so the other two edges of that cycle provide an alternate path between its endpoints. Edge \(34\) has no alternate path from \(3\) to \(4\). The general bridge criterion accounts for both outcomes.
Common Pitfall: A Bridge Need Not Isolate a Vertex
A common mistake is to interpret “bridge” as an edge whose removal leaves one endpoint isolated. The definition only requires that the number of connected components increases. In the path example, removing \(23\) leaves \(2\) connected to \(1\), and \(3\) connected to \(4\) and \(5\). Neither endpoint is isolated, but they are disconnected from each other, so the edge is a bridge.
Another mistake is to look only at whether an edge is part of a short cycle. The relevant question is whether its endpoints have any alternate path after the edge is removed. An edge on a cycle has such a path: follow the rest of the cycle between its endpoints. Conversely, the bridge criterion proves that an edge with no alternate path is a bridge. In a tree, uniqueness of paths rules out every such alternative, which is exactly why every tree edge is a bridge.
These distinctions are useful when examining a graph’s connectivity edge by edge. They also keep the claim precise: removing a bridge separates its endpoints, but it need not leave either endpoint isolated; removing an edge that is not a bridge may still change the graph, but it does not increase the number of components.
Check Your Understanding
For each question, justify your answer using the bridge criterion or the unique-path property.
- Let \(T\) have vertex set \(\{a,b,c,d\}\) and edge set \(\{ab,bc,cd\}\). After deleting \(bc\), give the vertex sets of the components.
- In a graph \(G\), an edge \(uv\) is on a cycle. Explain why that edge is not a bridge.
- Can deleting a bridge leave both endpoints with positive degree? Give an explicit graph and identify the components after deletion.
- Why does the proof that every tree edge is a bridge fail if the graph has a cycle?
- What does the statement “every edge of a single-vertex tree is a bridge” mean, given that the graph has no edges?