How a Graph Splits at Its Vertices
A graph can be connected and still have a small group of vertices whose removal splits it into separate pieces. Such a set identifies a structural weakness: paths between some vertices are forced through the set. Vertex separations describe this phenomenon by recording two overlapping parts of a graph and ruling out edges directly between their non-overlapping portions. Their order, the size of the overlap, gives a precise way to compare how robustly connected graphs are.
Throughout, graphs are finite and simple. A graph is connected if every two of its vertices are joined by a path. For a vertex set \(S\), \(G-S\) denotes the graph obtained by deleting the vertices in \(S\) and all edges incident with them. A graph is disconnected if it has at least two connected components.
The two sets \(A\) and \(B\) are allowed to overlap: vertices in the overlap are the vertices through which the two sides can meet. In a proper separation, deleting that overlap leaves vertices on both sides and no edges between them. Thus, in a connected graph, the overlap is a set whose deletion disconnects the graph. A set \(S\) whose deletion disconnects a connected graph is called a vertex separator; a separator consisting of one vertex is a cut vertex.
A vertex separation is a compact way of recording a decomposition. Each side \(G[A]\) and \(G[B]\) is an induced subgraph, meaning it contains all edges of \(G\) whose endpoints both lie in that side. There are no edges between \(A\setminus B\) and \(B\setminus A\), so every edge of \(G\) lies in at least one of these two induced subgraphs. Consequently, \(G\) is the union of \(G[A]\) and \(G[B]\), and their shared vertices are exactly \(A\cap B\).
Connectivity of Order Two and Three
The lower bound on the number of vertices is part of the definition. It prevents small complete graphs from satisfying a deletion condition vacuously. In particular, \(K_3\) is 2-connected but is not 3-connected, and \(K_2\) is not 2-connected. A 3-connected graph is necessarily 2-connected, since the 3-connectivity condition includes deletion of any single vertex.
Proof. First suppose that \(G\) is \(k\)-connected. It is connected, since deleting the empty set is deleting fewer than \(k\) vertices. If there were a proper separation \((A,B)\) of order less than \(k\), let \(S=A\cap B\). By propriety, both \(A\setminus B\) and \(B\setminus A\) are nonempty. In \(G-S\), these sets cover all the remaining vertices, and the separation condition says there is no edge between them. Thus \(G-S\) is disconnected. But \(|S|<k\), contradicting \(k\)-connectivity.
Conversely, suppose \(G\) is connected and has no proper separation of order less than \(k\). Assume for contradiction that some set \(S\), with \(|S|<k\), makes \(G-S\) disconnected. Partition the components of \(G-S\) into two nonempty groups, and let \(X\) and \(Y\) be the respective unions of their vertex sets. Then \(X\) and \(Y\) are nonempty, disjoint, and cover \(V(G)\setminus S\), with no edge between them: an edge between different components would join those components. Set \(A=X\cup S\) and \(B=Y\cup S\). These sets cover \(V(G)\), have \(A\cap B=S\), and have no edge between \(A\setminus B=X\) and \(B\setminus A=Y\). Therefore \((A,B)\) is a proper separation of order \(|S|<k\), a contradiction. Hence deleting any fewer than \(k\) vertices leaves \(G\) connected, as required. \(\square\)
This characterization gives a useful way to read small separators. A proper separation of order one witnesses failure of 2-connectivity. A proper separation of order two witnesses failure of 3-connectivity, even if the graph has no cut vertex. To establish 3-connectivity, it is not enough to check one-vertex deletions: every possible two-vertex deletion must also leave a connected graph.
Worked Separations
Worked Example: Two Triangles Sharing a Vertex
Let \(G\) have vertex set \(V(G)=\{1,2,3,4,5\}\) and edge set \(E(G)=\{12,23,13,34,45,35\}\). The triangles \(1,2,3\) and \(3,4,5\) share vertex \(3\). Consider \(A=\{1,2,3\}\) and \(B=\{3,4,5\}\).
The union is \(A\cup B=\{1,2,3,4,5\}=V(G)\), and the intersection is \(A\cap B=\{3\}\), so the separation has order \(1\). Its exclusive sides are \(A\setminus B=\{1,2\}\) and \(B\setminus A=\{4,5\}\). The edges \(12,23,13\) lie in \(G[A]\), while \(34,45,35\) lie in \(G[B]\); none joins the two exclusive sides. Therefore \((A,B)\) is a proper separation.
Check: Deleting the separator gives \(G-\{3\}\), with vertex set \(\{1,2,4,5\}\) and edges \(12,45\). Its two components are \(\{1,2\}\) and \(\{4,5\}\). The original graph is connected, but it is not 2-connected because deleting one vertex disconnects it.
Worked Example: A Cycle That Is 2-Connected but Not 3-Connected
Let \(G=C_5\), with \(V(G)=\{1,2,3,4,5\}\) and \(E(G)=\{12,23,34,45,51\}\). Deleting vertex \(1\) leaves the path \(2,3,4,5\), which is connected. By the symmetry of the cycle, deleting any one vertex leaves a path on four vertices. The graph itself is connected and has five vertices, so it is 2-connected.
Now take \(S=\{1,3\}\). The remaining vertices are \(\{2,4,5\}\), and the only remaining edge is \(45\). Thus \(\{2\}\) and \(\{4,5\}\) are separate components of \(G-S\). The corresponding separation is \(A=\{1,2,3\}\), \(B=\{1,3,4,5\}\): the union is all five vertices, the intersection is \(S\), and there is no edge between the exclusive sides \(\{2\}\) and \(\{4,5\}\). It is a proper separation of order \(2\).
Check: The graph remains connected after deleting any single vertex, but deleting the two vertices \(1\) and \(3\) disconnects it. Therefore it is 2-connected and not 3-connected. The separation test agrees: it has no proper separation of order less than \(2\), but it does have one of order \(2\).
Worked Example: A Separating Pair in a Four-Vertex Graph
Let \(G\) have \(V(G)=\{1,2,3,4\}\) and \(E(G)=\{13,14,23,24,34\}\). This is \(K_4\) with edge \(12\) absent. Consider \(S=\{3,4\}\), \(A=\{1,3,4\}\), and \(B=\{2,3,4\}\). We have \(A\cup B=V(G)\), \(A\cap B=S\), and the exclusive sides are \(\{1\}\) and \(\{2\}\). There is no edge \(12\), so there is no edge between the exclusive sides. This is a proper separation of order \(2\).
To determine whether the graph is 2-connected, check each single-vertex deletion. Deleting \(1\) leaves edges \(23,24,34\), a triangle; deleting \(2\) leaves edges \(13,14,34\), also a triangle. Deleting \(3\) leaves edges \(14,24\), which form the path \(1,4,2\). Deleting \(4\) leaves edges \(13,23\), which form the path \(1,3,2\). Every resulting graph is connected. Since the original graph is connected and has four vertices, it is 2-connected.
Check: Deleting \(S=\{3,4\}\) leaves vertices \(\{1,2\}\) and no edges, so the graph is not 3-connected. The order-two separation records exactly this disconnection.
Worked Example: Why \(K_4\) Is 3-Connected
Let \(G=K_4\), with \(V(G)=\{1,2,3,4\}\) and \(E(G)=\{12,13,14,23,24,34\}\). The graph is connected. Deleting no vertices leaves \(K_4\); deleting one vertex leaves a \(K_3\); deleting two vertices leaves a \(K_2\). Each of these graphs is connected. These are all deletion sizes less than \(3\), so \(K_4\) is 3-connected.
Check: A proper separation of order less than \(3\) would, by the theorem, contradict 3-connectivity. Directly, every pair of distinct vertices in \(K_4\) is joined by an edge, so no two nonempty exclusive sides can have no edge between them unless all vertices lie in the overlap. A proper separation therefore cannot have order \(0\), \(1\), or \(2\).
Common Pitfall: No Cut Vertex Does Not Mean 3-Connected
A common error is to check only whether a graph has a cut vertex and then conclude it is 3-connected. The cycle \(C_5\) above shows why this fails: no single vertex disconnects it, but the pair \(\{1,3\}\) does. Checking for cut vertices establishes 2-connectivity (when the graph is connected and has at least three vertices); 3-connectivity requires checking all vertex sets of size at most two.
For example, the incorrect argument “\(C_5\) has no cut vertex, so it is 3-connected” omits two-vertex deletions. The correction is to compute \(C_5-\{1,3\}\): its vertices are \(\{2,4,5\}\), its only edge is \(45\), and hence it is disconnected.
Finally, a vertex separator should not be confused with an edge cut. A vertex separator is deleted as a set of vertices, along with their incident edges; an edge cut is a set of edges whose deletion disconnects the graph. These can have different sizes and describe different ways in which a graph can split.
Check Your Understanding
For each question, state the relevant vertex sets and verify the separation or connectivity claim directly.
- For the graph with \(V=\{1,2,3,4\}\) and \(E=\{12,23,34,41\}\), give a proper separation of order \(2\), or explain why none exists.
- In the graph with \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,31,34,45,53\}\), identify the separator in the displayed decomposition into two triangles.
- Explain why a proper separation of order \(1\) in a connected graph proves that the graph is not 2-connected.
- For \(K_5\), explain why deleting any set of at most two vertices leaves a connected graph.
- Give an example of a graph that is 2-connected but not 3-connected, and identify a two-vertex separator.