Vertex Deletion and Connected Components
Removing a vertex can do more than shorten a graph: it can break one connected part into several pieces. A vertex whose removal causes this kind of separation is called a cut vertex. To identify one, compare the number of connected components before and after deleting the vertex. This comparison works for connected graphs and for disconnected graphs, provided the component counts are interpreted carefully.
All graphs in this tutorial are finite and simple. A path is a sequence of distinct vertices with consecutive vertices adjacent. Two vertices are connected if a path joins them. A connected component is a maximal set of vertices in which every pair is connected. An isolated vertex forms a component by itself. Write \(c(G)\) for the number of connected components of \(G\), and set \(c(G)=0\) when \(G\) has no vertices.
The strict inequality matters. Deleting a vertex may leave the component count unchanged, or may even reduce it. For example, deleting an isolated vertex removes one whole component; this does not make that vertex a cut vertex. In a connected graph with at least two vertices, the definition says exactly that deleting the vertex leaves at least two components.
Why the Component Count Changes
Proof. Before deletion, \(C\) contributes one component to \(c(G)\). Every other component of \(G\) has no vertex equal to \(v\), so none of those components changes when \(v\) is deleted. The vertices of \(C\setminus\{v\}\), together with the edges of \(C\) that remain, form exactly \(k\) components. Thus the contribution of \(C\) changes from \(1\) to \(k\), while all other contributions stay the same. Therefore \(c(G-v)=c(G)-1+k\). By the definition, \(v\) is a cut vertex precisely when \(c(G)-1+k>c(G)\), which is equivalent to \(k>1\), or \(k\ge2\). If \(C=\{v\}\), then \(k=0\), in agreement with the formula: deleting \(v\) removes that component. \(\square\)
This result isolates the relevant part of the graph. Only the component containing \(v\) can split; other components are unchanged. If \(G\) is connected and has at least two vertices, deleting \(v\) leaves at least one vertex, so \(k\ge1\). In that setting, \(v\) is a cut vertex precisely when the remaining graph has at least two components.
A Systematic Test
For a small graph given by an edge list, test each vertex in turn. Delete the candidate and its incident edges, then find the connected components among the remaining vertices. Compare that number with the original component count. A component can be found by starting at an unassigned vertex and following edges to every vertex reachable from it; repeat from an unassigned vertex until none remain. This procedure counts components, rather than merely checking whether the remaining graph has an edge.
Record \(c(G)\), including isolated vertices as components.
Remove that vertex and all edges incident with it.
Find every component of the remaining graph, including any isolated vertices.
The candidate is a cut vertex exactly when the new count is strictly larger.
Worked Example: A Degree-Two Vertex That Is Not a Cut Vertex
Let \(G\) have vertex set \(V(G)=\{1,2,3,4\}\) and edge set \(E(G)=\{12,23,34,41\}\). This is the 4-cycle. Determine whether vertex \(1\) is a cut vertex.
There is one component before deletion: all four vertices are joined around the cycle, so \(c(G)=1\). The edges incident with \(1\) are \(12\) and \(41\). Deleting \(1\) leaves vertices \(\{2,3,4\}\) and edges \(\{23,34\}\). The remaining vertices form the path \(2,3,4\), so they are all in one component and \(c(G-1)=1\). Since \(1\) is not greater than \(1\), vertex \(1\) is not a cut vertex.
In fact, every vertex of this graph has degree \(2\), and deleting any one leaves a path on the other three vertices. Each such deletion leaves one component. Check: before deletion, \(c(G)=1\); after deleting \(1\), the explicit path \(2,3,4\) gives \(c(G-1)=1\). Thus the component count does not increase.
Worked Example: Testing Every Vertex in a Connected Graph
Let \(G\) have \(V(G)=\{1,2,3,4,5\}\) and \(E(G)=\{12,23,13,34,45\}\). The vertices \(1,2,3\) form a triangle, and the path \(3,4,5\) is attached to it. The graph is connected, so \(c(G)=1\). Test each possible deletion.
Deleting \(1\) leaves edges \(23,34,45\), which join all remaining vertices in the path \(2,3,4,5\); the count is \(1\). Deleting \(2\) leaves edges \(13,34,45\), which join all remaining vertices in the path \(1,3,4,5\); the count is also \(1\). Deleting \(3\) leaves vertices \(1,2,4,5\) and edges \(12,45\), giving components \(\{1,2\}\) and \(\{4,5\}\); the count is \(2\). Deleting \(4\) leaves the triangle on \(\{1,2,3\}\) and the isolated vertex \(5\), giving \(2\) components. Deleting \(5\) leaves the connected graph on \(\{1,2,3,4\}\) with triangle edges \(12,23,13\) and edge \(34\), giving \(1\) component.
| Deleted vertex | Components after deletion | \(c(G-v)\) | Cut vertex? |
|---|---|---|---|
| 1 | \(\{2,3,4,5\}\) | 1 | No |
| 2 | \(\{1,3,4,5\}\) | 1 | No |
| 3 | \(\{1,2\},\{4,5\}\) | 2 | Yes |
| 4 | \(\{1,2,3\},\{5\}\) | 2 | Yes |
| 5 | \(\{1,2,3,4\}\) | 1 | No |
The table tests all five vertices, and the only strict increases from \(c(G)=1\) occur for \(3\) and \(4\). Therefore these, and only these, are cut vertices. Check: deleting \(3\) leaves precisely the edge \(12\) on \(\{1,2\}\) and the edge \(45\) on \(\{4,5\}\), so the count is \(2>1\); deleting \(4\) leaves a triangle and an isolated vertex, also \(2>1\).
Worked Example: Cut Vertices in a Disconnected Graph
Let \(G\) have \(V(G)=\{a,b,c,d,e,f\}\) and \(E(G)=\{ab,bc,ca,de\}\). Its components are the triangle \(\{a,b,c\}\), the edge component \(\{d,e\}\), and the isolated vertex \(\{f\}\). Hence \(c(G)=3\). Consider deleting \(b\), \(f\), or \(d\).
Deleting \(b\) leaves \(a\) and \(c\) with no edge between them, the component \(\{d,e\}\), and the isolated vertex \(\{f\}\). Thus there are four components and \(c(G-b)=4>3\), so \(b\) is a cut vertex.
Deleting \(f\) removes the isolated component and leaves the triangle and the edge component. Therefore \(c(G-f)=2<3\), so \(f\) is not a cut vertex. Deleting \(d\) leaves the triangle, the isolated vertex \(e\), and the isolated vertex \(f\). This gives \(c(G-d)=3\), equal to the original count, so \(d\) is not a cut vertex. Check: the counts are \(4\), \(2\), and \(3\), respectively, compared with the original \(3\); only deletion of \(b\) strictly increases the count.
What the Definition Does—and Does Not—Say
A cut vertex is defined by a change in the number of components, not merely by whether the remaining graph looks “less connected.” This distinction is especially important when the original graph is disconnected. Deleting a vertex from one component cannot alter the other components, but it can split the vertex’s own component, remove that component, or leave its component count unchanged.
For example, the isolated vertex \(f\) in the previous graph is not a cut vertex, even though deleting it changes the graph: it reduces the number of components from \(3\) to \(2\). Likewise, a vertex of degree \(2\) need not be a cut vertex, as the 4-cycle example shows. Degree alone does not determine the answer. A reliable test always compares the two component counts.
For a connected graph \(G\) with at least two vertices, there is a convenient equivalent test: delete \(v\) and ask whether the remaining graph is disconnected. Indeed, before deletion \(c(G)=1\), and at least one vertex remains. Thus \(c(G-v)\ge1\), and the inequality \(c(G-v)>1\) holds exactly when at least two components remain. This equivalence uses connectedness of the original graph; for a disconnected graph, “the remainder is disconnected” by itself does not tell whether the component count increased.
The empty graph convention also handles the smallest case without an exception to the definition. If \(G\) consists of a single vertex \(v\), then \(c(G)=1\), while \(G-v\) has no vertices and \(c(G-v)=0\). The strict increase required for a cut vertex does not occur, so the single vertex is not a cut vertex. The definition therefore gives consistent answers for isolated vertices, connected graphs, and disconnected graphs.
Common mistake: It is incorrect to call a vertex a cut vertex whenever deletion leaves a graph with more than one component. That rule ignores the number of components before deletion. In the disconnected example, deleting \(f\) leaves two components, but the original graph had three; the count fell from \(3\) to \(2\), so \(f\) is not a cut vertex. The correction is to calculate both \(c(G)\) and \(c(G-v)\), then test the strict inequality \(c(G-v)>c(G)\).
Check Your Understanding
For each question, use the component-count definition and include isolated vertices when counting.
- Let \(V(G)=\{1,2,3,4\}\) and \(E(G)=\{12,23,34\}\). Which vertices are cut vertices? Show the component count after deleting each one.
- Suppose \(G\) has four components and deleting \(v\) leaves five. What does this imply about \(v\), and how many components of the original component containing \(v\) remain after deletion?
- Let \(G\) consist of two disjoint edges \(ab\) and \(cd\). Is \(a\) a cut vertex? Compare the component counts before and after deleting it.
- Explain why deleting an isolated vertex cannot make the number of components increase.
- For a connected graph with at least two vertices, prove that \(v\) is a cut vertex if and only if \(G-v\) has at least two components.