From Graph Deletions to Topological Cut Points
A finite graph can be viewed as a topological space by replacing each edge with an interval and gluing its endpoints to the corresponding vertices. This turns a question about deleting a vertex into a question about deleting a point of a space. The correspondence is close, but not every cut point comes from a vertex: deleting an interior point of a bridge also disconnects the realization.
Throughout, a graph \(G=(V,E)\) is finite, undirected, and simple: it has no loops or multiple edges. A graph path is a finite sequence of vertices in which consecutive vertices are joined by an edge. A graph is connected if every pair of its vertices can be joined by a graph path. Its geometric realization, denoted \(|G|\), is obtained from one copy of \([0,1]\) for each edge, attaching the two endpoints to the vertices incident to that edge. We give \(|G|\) the quotient topology from these intervals and the vertices. A topological space is connected if it cannot be written as a union of two disjoint, nonempty open sets.
For a connected graph with at least two vertices, deleting a vertex leaves at least one vertex, so the definition of a cut vertex causes no empty-graph ambiguity. A graph with just one vertex has no cut points in its realization: deleting its sole point leaves the empty space, which is not disconnected.
Why Graph Paths Describe the Realization
The key link is that graph paths become continuous paths in \(|G|\): traverse each edge interval between its endpoints, then concatenate the resulting finitely many paths. Conversely, the pieces of the realization can connect different vertices only through edges joining them. We will use the following precise consequence.
Proof. If \(G\) is connected, any two vertices are joined by a graph path, which gives a continuous path between them in \(|G|\). A point in the interior of an edge can also be joined along that edge to either endpoint. Thus any two points of \(|G|\) can be joined by first moving to vertices, following a graph path, and then moving along an edge if necessary. So \(|G|\) is path-connected. A path-connected space is connected: if it had a separation into two nonempty open sets, a path from one set to the other would give a separation of the interval \([0,1]\) by preimages, contradicting the connectedness of \([0,1]\).
Conversely, suppose \(G\) is not connected. Partition its vertices into the vertex sets of its graph components. Each edge has both endpoints in one component. For each component, take its vertices together with all the edge intervals attached to them. These sets are disjoint, nonempty, and cover \(|G|\); each is open in \(|G|\), since points in edge interiors have interval neighborhoods within that set and small neighborhoods of each vertex use only its incident edges. There are at least two such sets, so they give a separation of \(|G|\). Thus \(|G|\) is not connected, and in particular is not path-connected. \(\square\)
The Cut-Point Classification
- It is a vertex \(v\) for which \(G-v\) is disconnected.
- It is in the interior of an edge \(e\) for which \(G-e\) is disconnected.
Proof. First consider a vertex \(v\). If \(G-v\) is connected, any two of its vertices can be joined by a graph path avoiding \(v\). A point on an edge not incident to \(v\) can be joined along that edge to one of its endpoints. A point on an edge incident to \(v\), after \(v\) is removed, lies on the remaining interval attached to the other endpoint; it can be joined to that endpoint. These routes show that \(|G|\setminus\{v\}\) is path-connected, so \(v\) is not a cut point.
If instead \(G-v\) has more than one graph component, assign to each component \(C\) the set \(Y_C\) consisting of its vertices, the full intervals for edges within \(C\), and the portions of intervals for edges from \(v\) to vertices of \(C\), with \(v\) removed. The sets \(Y_C\) are disjoint and cover \(|G|\setminus\{v\}\). Each is nonempty. Each is open in the space with \(v\) removed: an edge-interior point has a small interval neighborhood on its assigned side, and a remaining vertex has a neighborhood using only its incident edges, all of which lead to vertices in the same component \(C\), or to the removed point \(v\). Therefore one \(Y_C\) and the union of the others form a separation. Hence \(v\) is a cut point.
Now let \(p\) be in the interior of an edge \(e\). If \(G-e\) is connected, graph paths avoiding \(e\) join all vertices. Each of the two portions of \(e\) left after removing \(p\) attaches to one endpoint, so every remaining point can be joined to a vertex, and any two points can be joined by a path in \(|G|\setminus\{p\}\). Thus \(p\) is not a cut point.
If \(G-e\) is disconnected, it has exactly two components: starting from either endpoint of \(e\), every vertex is reachable without \(e\) on one side or the other, and any path joining the sides in \(G\) must use \(e\). In \(|G|\setminus\{p\}\), assign the remaining half of \(e\) at each endpoint to the component containing that endpoint, together with that component's vertices and edges. These two nonempty sets partition the space and are open there, by the interval neighborhoods at edge points and the neighborhoods at vertices. They separate \(|G|\setminus\{p\}\), so \(p\) is a cut point. Every point of \(|G|\) is either a vertex or an edge-interior point, completing both directions. \(\square\)
The theorem separates two mechanisms. A vertex is a cut point precisely when removing it disconnects the graph. An edge-interior point is a cut point precisely when the edge is a bridge. The second case matters because the realization contains more points than the graph's vertices.
Worked Example: A Four-Vertex Path
Let \(G\) have vertices \(v_1,v_2,v_3,v_4\) and edges \(v_1v_2,v_2v_3,v_3v_4\). Its realization is a chain of three intervals. Determine all its cut points.
Deleting \(v_1\) leaves the path \(v_2-v_3-v_4\), which is connected, so \(v_1\) is not a cut vertex. Deleting \(v_4\) leaves \(v_1-v_2-v_3\), also connected, so \(v_4\) is not a cut vertex. Deleting \(v_2\) leaves \(v_1\) separated from the edge \(v_3v_4\), so \(G-v_2\) is disconnected. Deleting \(v_3\) leaves the edge \(v_1v_2\) and the vertex \(v_4\) in different components. Thus \(v_2\) and \(v_3\), and only those vertices, are cut vertices.
Each of the three edges is a bridge: deleting any one breaks the chain into two nonempty parts. The theorem therefore says that every edge-interior point is a cut point, as are \(v_2\) and \(v_3\). The endpoints \(v_1,v_4\) are not cut points. This checks the distinction: not every point of a path realization is a cut point, even though every edge-interior point is one.
Worked Example: A Cycle
Let \(G\) be the four-cycle \(v_1v_2v_3v_4v_1\). For each vertex, deleting it leaves a path on the other three vertices, which is connected. For example, deleting \(v_1\) leaves \(v_2-v_3-v_4\). The same description holds after deleting any of the four vertices, so there are no cut vertices.
Deleting any one edge leaves the other three edges joined in a path through all four vertices. Thus no edge is a bridge. By the theorem there are no cut points in \(|G|\). In particular, deleting a point in an edge interior does not disconnect this realization: the rest of the cycle still supplies a route between the two sides of that edge.
Worked Example: A Triangle with a Pendant Edge
Take a triangle with vertices \(a,b,c\), and add a vertex \(d\) joined only to \(a\). The edges are \(ab,bc,ca,ad\). Deleting \(a\) leaves the isolated vertex \(d\) and the edge \(bc\), so \(G-a\) is disconnected and \(a\) is a cut vertex. Deleting \(b\) leaves the path \(d-a-c\), and deleting \(c\) leaves the path \(d-a-b\); both are connected. Deleting \(d\) leaves the triangle, which is connected. Therefore \(a\) is the only cut vertex.
The edge \(ad\) is a bridge because its deletion separates \(d\) from the triangle. None of the triangle's edges is a bridge: after deleting any one of them, the other two triangle edges still join its endpoints, and \(d\) remains attached at \(a\). Hence the cut points consist of the vertex \(a\) and all interior points of \(ad\). No interior point of a triangle edge is a cut point.
Trees, Paths, and a Common Pitfall
A tree is a connected graph with no cycles. In a tree, every edge is a bridge. Indeed, if an edge could be deleted while leaving the graph connected, its endpoints would still be joined by a path avoiding that edge; together with the deleted edge, this would form a cycle. Also, deleting a vertex \(v\) separates the tree into one component for each edge incident to \(v\): two different neighbors cannot remain connected without creating a cycle through \(v\). Consequently, in a tree with at least three vertices, a vertex is a cut vertex exactly when it has at least two incident edges. A vertex with just one incident edge leaves the rest connected when deleted.
Thus every edge-interior point of a tree realization is a cut point, while its vertex cut points are exactly the vertices of degree at least two. A path with at least three vertices has its internal vertices as cut points and its edge interiors as cut points, but not its endpoints. A cycle behaves oppositely: it has neither bridges nor cut vertices, so its realization has no cut points.
Common pitfall. It is incorrect to claim that every cut point of a graph realization must be a cut vertex. For the graph with two vertices joined by one edge, deleting either vertex leaves a single-vertex graph, which is connected; neither vertex is a cut vertex. But deleting the midpoint of the edge leaves two disjoint half-intervals. Equivalently, the sole edge is a bridge, so its midpoint is a cut point by the theorem. The correction is to test vertex deletions and edge deletions separately.
This classification is useful because the realization translates a topological deletion question into two finite graph checks. It also warns that the graph's vertex list alone does not record all cut points: bridges contribute an entire edge interior's worth of them.
Check Your Understanding
For each question, use both the graph deletion test and the classification theorem where appropriate.
- In a path with five vertices, which vertices are cut points of its realization, and which edge-interior points are cut points?
- Explain why no edge of a cycle is a bridge, including when the cycle has three vertices.
- A connected graph has a bridge \(e\). What does the theorem imply about every point in the interior of the interval representing \(e\)?
- For a tree with at least three vertices, prove that a leaf is not a cut vertex and that every vertex of degree at least two is a cut vertex.
- Can the realization of a connected graph with at least two vertices have a cut point at a vertex but no cut point in any edge interior? Justify your answer.