Global Connectivity as Resistance to Vertex Deletion
Global vertex connectivity measures how many vertices must be removed to destroy the connectedness of a graph. Its definition has two important conventions: a disconnected graph is assigned connectivity zero, while a complete graph is assigned connectivity one less than its order. The second convention matters because deleting vertices from a complete graph never leaves two or more disconnected components until fewer than two vertices remain.
Throughout, graphs are finite and simple. A graph is connected if every pair of its vertices is joined by a path; in particular, a graph with one vertex is connected. For \(S\subseteq V(G)\), \(G-S\) denotes the induced subgraph on \(V(G)\setminus S\). A set \(S\) is a vertex separator if \(G-S\) is disconnected. When referring to a separator for two particular vertices \(u\) and \(v\), we require \(u,v\notin S\) and that \(u\) and \(v\) lie in different components of \(G-S\).
For a connected noncomplete graph, a separator exists, as shown below. The complete-graph assignment is a convention that makes the parameter meaningful even though a complete graph has no vertex set whose deletion leaves at least two components. The bound \(\kappa(G)\le n-1\) is built into the definition for complete graphs; for connected noncomplete graphs, a separator can be chosen with at most \(n-2\) vertices.
Separators Exist in Connected Noncomplete Graphs
Proof. Since \(G\) is noncomplete, there are distinct nonadjacent vertices \(x\) and \(y\). Let \(S=N(x)\), the set of vertices adjacent to \(x\). Neither \(x\) nor \(y\) belongs to \(S\): a simple graph has no loop at \(x\), and \(x\) and \(y\) are nonadjacent. Thus \(x\) and \(y\) remain in \(G-S\). Every neighbor of \(x\) has been removed, so \(x\) is isolated in \(G-S\), while the distinct vertex \(y\) remains. Therefore \(G-S\) is disconnected. Since \(x\) and \(y\) are both outside \(S\), \(|S|\le n-2\). Hence \(S\) is a separator of the stated size. \(\square\)
This argument also explains the role of the complete-graph convention: for a connected noncomplete graph, there is a genuine separator, but for a complete graph there is no nonadjacent pair from which to construct one.
The Deletion Characterization
The upper restriction \(k\le n-1\) is essential, not cosmetic. Under that restriction, every deletion set being tested leaves at least two vertices when \(k\ge1\). In particular, for a complete graph the condition stops at \(k=n-1\); it does not incorrectly assign connectivity \(n\).
Proof. If \(k=0\), there are no sets \(S\) with \(|S|<0\), so the deletion condition is vacuously true, and \(\kappa(G)\ge0\) by the definition. Suppose now that \(1\le k\le n-1\). If \(G\) is disconnected, taking \(S=\varnothing\) shows that the deletion condition fails, and \(\kappa(G)=0<k\).
Suppose \(G\) is complete. For any \(S\) with \(|S|<k\), we have \(|S|\le k-1\le n-2\), so \(G-S\) is a complete graph with at least two vertices and is connected. Thus the deletion condition holds. Also \(\kappa(G)=n-1\ge k\).
It remains to consider connected, noncomplete \(G\). By the proposition, it has at least one vertex separator, so the minimum separator size defining \(\kappa(G)\) exists. If \(\kappa(G)\ge k\), no set of size less than \(k\) can be a separator; therefore every such \(G-S\) is connected. Conversely, if every \(G-S\) with \(|S|<k\) is connected, then no separator has size less than \(k\). The minimum separator size is therefore at least \(k\), which says \(\kappa(G)\ge k\). These cases prove both directions. \(\square\)
The theorem is a threshold test: to show \(\kappa(G)\ge k\), all deletions of fewer than \(k\) vertices must preserve connectedness. To show \(\kappa(G)<k\), it is enough to exhibit one set \(S\) with \(|S|<k\) for which \(G-S\) is disconnected. For \(k=0\), the first test has no deletion sets; for \(k\ge1\), the empty deletion is among the tests, so a disconnected graph cannot pass.
Worked Example: Connectivity of a Path
Let \(G\) have \(V(G)=\{1,2,3,4,5\}\) and \(E(G)=\{12,23,34,45\}\). This is the path \(P_5\). The graph is connected, since its listed edges give a path between any two vertices. It is not complete: for example, \(1\) and \(3\) are not adjacent.
Deleting the single vertex \(3\) leaves vertices \(\{1,2,4,5\}\) and edges \(\{12,45\}\). The remaining graph has two components, \(\{1,2\}\) and \(\{4,5\}\). Thus \(\{3\}\) is a separator, so \(\kappa(G)\le1\). The empty set is not a separator because \(G\) itself is connected, so there is no separator of size zero. Hence the minimum separator size is \(1\), and \(\kappa(G)=1\).
Check: For \(k=1\), the only set with \(|S|<1\) is \(S=\varnothing\), and \(G-S=G\) is connected. For \(k=2\), the set \(\{3\}\) has size less than \(2\) and disconnects the graph. The deletion characterization therefore agrees with \(\kappa(G)=1\).
Worked Example: Connectivity of a Cycle
Let \(G\) have \(V(G)=\{1,2,3,4,5\}\) and \(E(G)=\{12,23,34,45,51\}\), so \(G=C_5\). It is connected and noncomplete.
Deleting any one vertex leaves a path on the other four vertices. In detail, deleting \(1,2,3,4,5\), respectively, leaves the paths with vertex orders \(2,3,4,5\); \(3,4,5,1\); \(4,5,1,2\); \(5,1,2,3\); and \(1,2,3,4\). Each order uses the four remaining cycle edges consecutively, so each resulting graph is connected. The empty deletion also leaves the connected graph \(C_5\). Therefore every deletion of fewer than two vertices preserves connectedness, and the theorem gives \(\kappa(G)\ge2\).
Now delete \(S=\{1,3\}\). The remaining vertex set is \(\{2,4,5\}\), and the remaining edge set is \(\{45\}\). The components are \(\{2\}\) and \(\{4,5\}\), so this deletion disconnects the graph. Thus \(\kappa(G)<3\). Combining the bounds gives \(\kappa(G)=2\).
Check: The two-vertex deletion has size \(2\), and \(G-S\) has exactly the isolated vertex \(2\) and the edge \(45\). This verifies directly that the exhibited set is a separator, while the single-vertex checks establish that no smaller set is one.
Worked Example: A Disconnected Graph
Let \(G\) have \(V(G)=\{1,2,3,4,5\}\) and \(E(G)=\{12,23,31,45\}\). The vertices \(\{1,2,3\}\) form a triangle, and \(\{4,5\}\) form a separate edge; there is no edge between these two sets. Hence \(G\) is disconnected before any vertices are removed, and the definition gives \(\kappa(G)=0\).
The empty set already witnesses the failure of connectedness: \(G-\varnothing=G\) has two components. The deletion characterization also checks this value. For \(k=0\), it makes no deletion tests and is vacuously true. For \(k=1\), it tests \(S=\varnothing\), and the test fails. Thus \(\kappa(G)\ge0\) but \(\kappa(G)\not\ge1\), as required.
Complete Graphs and the Boundary Convention
For \(K_n\), deleting \(s\) vertices leaves \(K_{n-s}\). If at least one vertex remains, the result is connected under the convention that a single-vertex graph is connected. Consequently, no deletion of fewer than \(n-1\) vertices disconnects \(K_n\); the assigned value is \(\kappa(K_n)=n-1\).
Worked Example: Why the Range Stops at \(n-1\)
Let \(G=K_4\), with \(V(G)=\{1,2,3,4\}\) and \(E(G)=\{12,13,14,23,24,34\}\). By convention, \(\kappa(G)=4-1=3\). For every set \(S\) with \(|S|<3\), at least two vertices remain. The remaining graph is complete, hence connected. In particular, deleting two vertices leaves a \(K_2\), which is connected.
If one incorrectly used the deletion criterion with \(k=4\), every set \(S\) of size less than \(4\) would be tested. Such a set leaves at least one vertex, and the remaining graph is either \(K_4,K_3,K_2\), or \(K_1\); each is connected. The condition would therefore hold and would falsely suggest \(\kappa(K_4)\ge4\). The correct theorem restricts \(k\) to \(k\le n-1=3\), so this false conclusion is excluded. The case \(|S|=4\) is not tested at \(k=4\), since the condition is \(|S|<4\), not \(|S|\le4\); in any event, the issue is that testing up to \(k=n\) would count deletion to a single vertex as preserving connectedness.
Check: At the permitted boundary \(k=3\), the largest tested deletion has size \(2\), leaving \(4-2=2\) vertices. Every such remaining graph is \(K_2\) and is connected. The assigned value \(3\) therefore passes the criterion at \(k=3\), exactly as intended.
Common Pitfall and Practical Interpretation
A frequent mistake is to define \(\kappa(G)\) as the minimum size of a set whose deletion disconnects \(G\), without adding a convention for complete graphs. Under the definition of vertex separator used here, \(K_n-S\) is always complete when nonempty, so no such set disconnects \(K_n\). The minimum would not exist. The assigned value \(n-1\) resolves this exception and matches the deletion-resilience interpretation up to the largest meaningful threshold.
Wrong calculation: For \(K_4\), observe that \(K_4-S\) is connected for every \(|S|<4\), then conclude from the deletion test that \(\kappa(K_4)\ge4\). Correction: the deletion characterization applies only when \(k\le n-1\). Here \(n-1=3\), and the convention gives \(\kappa(K_4)=3\). The condition for \(k=4\) is not a valid connectivity test: it includes deletion of three vertices, leaving the connected graph \(K_1\), and would exceed the prescribed maximum value.
For a connected noncomplete graph, \(\kappa(G)\) gives the size of a smallest vertex set whose removal disconnects it. For a disconnected graph, the value zero records that no deletion is needed to lose connectedness. For a complete graph, the value \(n-1\) records the exceptional boundary convention. Keeping these cases separate prevents confusion between a genuine separator and the numerical value assigned to the global parameter.
Check Your Understanding
Use the definitions and the permitted range of the deletion characterization in your answers.
- Let \(G\) be the path on four vertices. Exhibit a minimum vertex separator and determine \(\kappa(G)\).
- Why does deleting two vertices from \(C_5\) suffice to show \(\kappa(C_5)<3\), but not by itself establish that \(\kappa(C_5)=2\)?
- State the deletion characterization for a graph of order \(n\), including the allowed values of \(k\) and the strict inequality on \(|S|\).
- For \(K_5\), what is the largest permitted value of \(k\) in the characterization, and how many vertices remain after a deletion of size \(k-1\)?
- Explain why the empty deletion set shows that a disconnected graph does not satisfy the criterion for any \(k\ge1\).