Two Different Kinds of Separation
Deleting a vertex can separate a graph even when none of the edges touching that vertex is individually responsible for the separation. Conversely, a single edge can be a bridge without either endpoint being a cut vertex. To understand how these situations interact, examine the components left behind when a vertex is removed: each such component attaches back to the vertex through one or more incident edges.
All graphs in this tutorial are finite and simple. A graph is connected if every pair of vertices is joined by a path. Write \(c(G)\) for the number of connected components of \(G\), with \(c(G)=0\) when \(G\) has no vertices. The notation \(G-v\) means delete \(v\) and all its incident edges; \(G-e\) means delete only the edge \(e\). A cycle is a closed sequence of at least three edges whose vertices, other than the repeated starting vertex, are distinct.
These definitions also handle disconnected graphs: components not containing the deleted vertex or edge remain unchanged. A single isolated vertex is not a cut vertex, since deleting it changes the component count from \(1\) to \(0\), rather than increasing it.
Components After Deleting a Vertex
Now suppose \(G\) is connected and \(v\in V(G)\). Every component \(C\) of \(G-v\) must have at least one vertex adjacent to \(v\); otherwise \(C\) would already have been disconnected from \(v\) in \(G\). Call the vertices of \(C\) adjacent to \(v\) the attachment vertices of \(C\), and write their set as \(A_C\).
Proof. First suppose \(A_C=\{u\}\). The only edge from \(C\) to \(v\) is then \(vu\), and there are no edges from \(C\) to any other component of \(G-v\). After deleting \(vu\), there is no path from a vertex in \(C\) to \(v\), so the graph becomes disconnected. Thus \(vu\) is a bridge.
Now suppose \(|A_C|\ge 2\). Take any \(u\in A_C\), and choose a different vertex \(w\in A_C\). Since \(C\) is connected, it contains a path from \(u\) to \(w\). That path, together with the edges \(wv\) and \(vu\), forms a cycle containing \(vu\). In particular, deleting \(vu\) does not disconnect the graph: the rest of this cycle still joins its endpoints. Thus \(vu\) is not a bridge, and the argument applies to every edge from \(v\) to \(C\). \(\square\)
The criterion separates two possibilities within each component of \(G-v\). A component joined to \(v\) by exactly one edge contributes an incident bridge. A component joined by two or more edges contributes no incident bridges, and all of its edges to \(v\) lie on cycles. The number of components of \(G-v\), meanwhile, determines whether \(v\) is a cut vertex. These are related but distinct tests.
Worked Example: A Cut Vertex with No Incident Bridges
Let \(G\) have vertex set \(V=\{x,a,b,c,d\}\) and edge set \(E=\{xa,ab,bx,xc,cd,dx\}\). This graph consists of two triangles that share the vertex \(x\). Determine whether \(x\) is a cut vertex, and classify its incident edges.
Deleting \(x\) removes the edges \(xa,bx,xc,dx\). The remaining edges are \(ab\) and \(cd\), so the components of \(G-x\) have vertex sets \(\{a,b\}\) and \(\{c,d\}\). Thus \(c(G)=1\), while \(c(G-x)=2\), and \(x\) is a cut vertex.
For the component \(\{a,b\}\), the attachment vertices are \(A_{\{a,b\}}=\{a,b\}\). There are two attachments, and the edges \(xa\) and \(xb\) lie on the cycle \(x,a,b,x\). For the component \(\{c,d\}\), the attachments are \(A_{\{c,d\}}=\{c,d\}\), and \(xc\) and \(xd\) lie on the cycle \(x,c,d,x\). Therefore every edge incident with the cut vertex \(x\) lies on a cycle; none is a bridge.
Check: The edge list contains exactly the six edges of the two listed triangles. Deleting any one of these edges leaves the other two edges of its triangle as a path between its endpoints, so that deletion does not disconnect \(G\). This verifies directly that none is a bridge.
When a Cut Vertex Is Incident with a Bridge
A cut vertex can also have a mixture of incident edges: some lie on cycles, while others are bridges. The attachment criterion identifies this mixture one component at a time. In particular, it is not enough to know only that \(v\) is a cut vertex. One must check how many edges from \(v\) reach each component of \(G-v\).
Worked Example: A Cut Vertex with Both Types of Incident Edge
Let \(G\) have \(V=\{a,b,c,d,e\}\) and \(E=\{ab,bc,ca,cd,de\}\). The vertices \(a,b,c\) form a triangle, and \(c,d,e\) extend it by a path. Classify the cut vertices and bridges, and examine the edges incident with \(c\) and \(d\).
Deleting \(c\) leaves the edge \(ab\) and the edge \(de\), on disjoint vertex sets \(\{a,b\}\) and \(\{d,e\}\). Hence \(c(G-c)=2>1=c(G)\), so \(c\) is a cut vertex. The component \(\{a,b\}\) attaches to \(c\) at both \(a\) and \(b\); consequently \(ca\) and \(cb\) lie on the cycle \(c,a,b,c\). The component \(\{d,e\}\) attaches to \(c\) only through \(d\), so \(cd\) is a bridge.
Deleting \(d\) leaves the connected triangle on \(\{a,b,c\}\) and the isolated vertex \(e\). Thus \(d\) is also a cut vertex. In \(G-d\), the component \(\{a,b,c\}\) attaches to \(d\) only at \(c\), and the component \(\{e\}\) attaches only at \(e\). Therefore both incident edges \(cd\) and \(de\) are bridges. Deleting \(a\), \(b\), or \(e\) does not increase the number of components: the remaining graph is connected in each case. So these are the only cut vertices.
Check: The edges \(ab,bc,ca\) lie on the displayed triangle. Neither \(cd\) nor \(de\) lies on a cycle, because each is the only edge connecting the vertices on one side of that edge to the rest of the graph. Deleting either one separates the graph, as the attachment test predicts.
Which Endpoints of a Bridge Are Cut Vertices?
A bridge does not automatically make both its endpoints cut vertices. The answer depends on how many vertices lie on each side of the bridge. The following result gives the exact test in a connected graph.
Proof. Since \(e\) is a bridge, \(G-e\) has two components; call the one containing \(u\) \(A\), and the one containing \(v\) \(B\). When \(u\) is deleted from \(G\), the vertices of \(B\) remain connected to one another, because \(B\) was connected and its internal edges are unchanged. There is no edge from \(B\) to \(A-\{u\}\): such an edge would still connect the two components of \(G-e\), while the only edge between \(A\) and \(B\) in \(G\) is \(e\). Thus \(G-u\) has the component \(B\), together with the components of \(A-\{u\}\). If \(A=\{u\}\), there are no other components, so \(c(G-u)=1=c(G)\) and \(u\) is not a cut vertex. If \(A\) contains another vertex, then \(A-\{u\}\) has at least one component, separate from \(B\); hence \(c(G-u)\ge2>1=c(G)\), and \(u\) is a cut vertex. Interchanging \(u\) and \(v\) proves the statement for \(v\). \(\square\)
Worked Example: A Bridge with Just One Cut-Vertex Endpoint
Let \(G\) have \(V=\{1,2,3\}\) and \(E=\{12,23\}\). Determine the cut vertices and bridges, and use the endpoint test on each edge.
Deleting vertex \(2\) leaves the two isolated vertices \(1\) and \(3\). Thus \(c(G-2)=2>1=c(G)\), and \(2\) is a cut vertex. Deleting \(1\) leaves the edge \(23\), and deleting \(3\) leaves the edge \(12\); both resulting graphs are connected. So \(1\) and \(3\) are not cut vertices.
Deleting edge \(12\) leaves vertex \(1\) isolated and the edge \(23\), making two components. Deleting \(23\) likewise leaves two components. Both edges are bridges. For edge \(12\), the components after its deletion are \(\{1\}\) and \(\{2,3\}\). The side containing endpoint \(1\) has one vertex, so \(1\) is not a cut vertex; the side containing endpoint \(2\) has two vertices, so \(2\) is a cut vertex. For edge \(23\), the sides are \(\{1,2\}\) and \(\{3\}\), giving the same conclusion for its endpoints.
Check: The edge list has two edges, and deleting either one leaves exactly one edge and one isolated vertex, so the component count is \(2\). Deleting \(2\) leaves two isolated vertices, while deleting either endpoint \(1\) or \(3\) leaves a single edge. These direct counts agree with the classifications.
Common Pitfalls and Why the Distinction Matters
Confusing a cut vertex with an incident bridge. The first example has a cut vertex whose incident edges all lie on cycles. A mistaken argument might say, “Since deleting \(x\) disconnects the graph, every edge at \(x\) must be a bridge.” That conclusion is false: in the first example, deleting \(xa\) leaves the path \(x,b,a\), and deleting \(xc\) leaves the path \(x,d,c\). The correction is to test each incident edge by its component’s attachment set, rather than infer its status from the status of the vertex.
Assuming both endpoints of a bridge are cut vertices. In the third example, \(12\) is a bridge, but endpoint \(1\) is not a cut vertex. The erroneous calculation is to note that deleting \(12\) increases the component count and conclude that deleting either endpoint must also do so. Edge deletion and vertex deletion are different operations. The correction is to inspect the two sides of the bridge: a side consisting only of its endpoint disappears when that endpoint is deleted, leaving no second component on that side.
These distinctions are useful when diagnosing how a connected graph separates. A cut vertex records separation caused by removing a location; a bridge records separation caused by removing a connection. The attachment criterion connects them precisely without identifying them: singleton attachment sets give bridges, whereas two or more attachments place the incident edges on cycles. For a bridge, the sizes of its two sides then determine which endpoints are cut vertices.
Check Your Understanding
Use component counts and attachment sets to justify each answer.
- Let \(V=\{p,q,r,s,t\}\) and \(E=\{pq,qr,rp,rs,st,tr\}\). Is \(r\) a cut vertex? Are its incident edges bridges?
- In a connected graph, suppose a component \(C\) of \(G-v\) has exactly one attachment vertex. Explain why the edge from \(v\) to that vertex is a bridge.
- Give a connected graph with a cut vertex that has both an incident bridge and an incident edge lying on a cycle. Specify its vertex and edge sets.
- A bridge separates a connected graph into vertex sets of sizes \(1\) and \(6\). Which endpoint, if either, must be a cut vertex? Explain.
- Can a cut vertex have all its incident edges on cycles? Give an example and verify both properties by deletion or by the attachment criterion.