Motivation
A local path theorem compares one chosen pair of vertices. Global vertex connectivity asks whether the entire graph remains connected when a small collection of vertices fails. The two viewpoints are related, but the adjacent-endpoint exception in the local separator theorem cannot simply be ignored: deleting internal vertices can never remove an edge joining the endpoints themselves.
We will handle that exception explicitly, obtaining disjoint routes for every pair in a globally connected graph. A second construction replaces one destination by a set of possible destinations. It produces a fan whose paths meet only at their common starting vertex, with different endpoints in the target set. The proofs reveal why both the size of the graph and the number of distinct targets belong in the hypotheses.
The only imported result is the finite nonadjacent-endpoint vertex version of Menger's theorem proved in the preceding note; no stronger all-pairs statement is assumed.
Definitions
Definition 9.3.1
(Global vertex connectivity)
Let be a finite simple undirected graph and an integer. It is -vertex-connected, or -connected here, if and deleting any set of fewer than vertices leaves a connected graph. Deletion removes the chosen vertices and all incident edges.
Paths are simple. A family of paths from to is internally vertex-disjoint when any two share only their endpoints. Distinct paths are required; a direct edge can occur as only one path in such a family.
The order condition prevents declarations based on graphs that become empty or a singleton after all meaningful vertices have been deleted. Under the usual convention, a complete graph on vertices has vertex connectivity . Testing only nonadjacent pairs would say nothing at all about a complete graph, so it cannot replace the global definition by itself.
Definition 9.3.2
(A fan to a target set)
For a vertex and a target set , a -fan from to is a family of paths starting at , ending at distinct vertices of , and otherwise pairwise disjoint. We additionally require that no interior vertex of any fan path belongs to ; truncating at its first target enforces this convention.
The earlier local theorem says that for distinct nonadjacent endpoints, the maximum number of internally vertex-disjoint paths equals the minimum size of a vertex set, excluding the endpoints, whose deletion separates them. All graphs to which that result is applied below are finite, simple and have the required nonadjacency.
Theorem/Proposition
Theorem 9.3.3
(Global connectivity is equivalent to disjoint routes for every pair)
Suppose . The graph is -connected if and only if every pair of distinct vertices has at least internally vertex-disjoint paths between them. Adjacent pairs are included in this statement. Consequently every vertex of a -connected graph has degree at least .
Lemma 9.3.4
(Fan lemma and a converse criterion)
In a -connected graph, for every vertex and every target set not containing with , there is a -fan from to .
Conversely, if a graph has at least vertices and such a fan exists for every and every -element target set avoiding , then the graph is -connected. The converse uses the universal choice of target sets, not merely one particularly favorable set.
Concept lensStructural
Local certificates measure a global deletion promise
Connectivity quantifies over every small failed set. Menger converts the promise into many independent routes for each pair. In the proof below, adding one auxiliary destination converts a target set into a single-pair question, then truncation restores distinct original destinations. The auxiliary vertex is a proof device, not an extra resource left in the original graph.
The degree conclusion is necessary, not sufficient. Likewise many disjoint paths between one selected pair do not establish the all-pairs property. The fan gives distinct target endpoints; allowing every path to terminate at one target would express a different, much weaker requirement.
Proof sketch or proof idea
Proof
(Disjoint routes for every pair, including adjacent endpoints)
First suppose every pair has internally disjoint paths. Delete a set with and choose any two vertices outside it. A deleted vertex can lie internally on at most one of those paths. Thus fewer than paths can be destroyed and at least one survives. Every remaining pair is connected, proving the global deletion property.
Now suppose is -connected. Nonadjacent endpoints cannot be separated by fewer than other vertices, so the local theorem immediately supplies paths. Adjacent endpoints require an additional argument. For , their edge supplies the one required path. Let , let be an edge and put , keeping every vertex.
We claim that no set of at most other vertices separates from in . If such a set existed, would be connected, while adding the single edge to would join its components. Hence would have exactly two components, one containing each endpoint. There are at least three vertices left, because . At least one component therefore contains an additional vertex beyond its endpoint.
If the component containing has such an additional vertex, delete from . That additional vertex remains separated from the nonempty component containing : the sole edge between the two components has disappeared. This contradicts -connectivity because . If instead the component containing has an additional vertex, delete and obtain the symmetric contradiction. Thus the claimed separator cannot exist.
Endpoints are nonadjacent in , so local Menger now supplies at least internally disjoint paths there. Adding the original one-edge path gives distinct internally disjoint paths in . This proves the all-pairs equivalence with the adjacent case included.
For the degree bound, suppose a vertex had fewer than neighbors. Deleting all those neighbors would isolate it, while the order condition leaves at least one other vertex. The remaining graph would be disconnected after fewer than deletions, a contradiction.
Proof X-ray
Deleting an edge makes the local theorem applicable
The direction from paths to connectivity is pure counting: a deleted vertex lies inside at most one path of the family, so fewer than deletions cannot destroy all routes. The other direction contains the one non-obvious move. Local Menger needs nonadjacent endpoints, and no internal separator can ever remove the edge , so the proof deletes first and asks for only routes in .
The separator bound in is where the hypotheses enter. Connectivity of is used twice: with it makes connected, so has exactly two components; with it forbids deleting or . The order condition is used once, to leave at least three vertices in , so that one side holds a vertex other than its endpoint. If only the two endpoints remained, deleting one of them would leave a single vertex and no contradiction. The argument closes by restoring as the -th path; its interior is empty, so it is internally disjoint from the other .
Proof
(An auxiliary target vertex, then a forced internal hit)
For the fan lemma, add a new vertex adjacent exactly to all vertices of . The endpoints are nonadjacent. Let be any set of fewer than other vertices in this enlarged graph. Since at least targets were available, choose . The original graph is connected and contains , so it has a route from to , followed by the new edge to . Therefore does not separate .
Local Menger in the enlarged graph gives internally disjoint -to- paths. Remove their final edges to and truncate each remaining path when it first enters . Their endpoints are distinct, since a common target would have been an internal intersection of the original paths. Their interiors avoid by the truncation, and no new intersection can be created by deleting suffixes. This is the required fan.
For the converse, suppose deleting some with disconnects the graph. Choose in one remaining component and in another. Choose a -element target set containing and avoiding ; the graph's order guarantees enough other vertices to fill it. Any -fan to this set must use all its targets, including . But every -to- path must pass through , which is part of the target set. It would meet a target internally before reaching , violating the fan definition. This contradiction rules out every separating set of size below and proves -connectivity.
Vertex failure differs from edge failure
A vertex deletion can simultaneously destroy many incident edges. A graph may therefore have no fragile individual edge while possessing a single vertex through which every route between two regions must pass. Conversely the degree bound compares local availability with global resilience: distinct internally disjoint routes must start through different neighbors, but having enough neighbors does not prevent a remote bottleneck.
The theorems give certificates in both directions. A path family proves that fewer internal deletions cannot separate its endpoints. A small separating set proves a global connectivity failure. A fan records a stronger routing arrangement to several individually identified targets. These objects should be checked as actual vertex sequences, rather than inferred from lines that seem separated in a drawing.
Worked examples
Worked example 9.3.5
(Complete graphs attain the order limit)
In , deleting fewer than vertices leaves at least two vertices and all edges between them, so the graph is -connected. For endpoints , use their direct edge and, for each of the other vertices , the two-edge path . These are exactly internally disjoint paths. Each endpoint has degree , so there cannot be a larger distinct family. The direct edge counts once despite having an empty internal-vertex set.
Worked example 9.3.6
(A cycle has two routes but not arbitrary resilience)
For a cycle with at least three vertices, deleting one vertex leaves a connected path. Hence it is two-connected. Between any endpoints, the two directions around the cycle give internally disjoint paths. Its degree is two, so it cannot satisfy a three-connected graph's degree condition when its order permits that condition; the triangle also fails the required order for three-connectivity. A long cycle is not more vertex-connected merely because it has more vertices.
Worked example 9.3.7
(A wheel provides three independent attachments)
Take a rim cycle with at least three vertices and a hub adjacent to every rim vertex. If at most two deleted vertices omit the hub, every surviving rim vertex still joins the hub. If the hub is deleted, at most one rim vertex is also deleted, leaving a connected rim or rim path. Thus the wheel is three-connected.
For a four-vertex rim and hub , a three-fan from to is ; ; and . Their target endpoints differ and their only common vertex is . This explicitly checks the fan, rather than only observing three paths leaving the source.
Common mistakes
Counterexample mode
Minimum degree two does not imply two-connectivity
Join two triangles at a single common vertex , with no other overlap or edges. Every vertex has degree at least two, and deleting any single edge leaves the graph connected. Yet deleting separates the other two vertices of one triangle from the other two vertices of the second. The graph is connected but not two-vertex-connected. Routes between opposite triangles all pass through the same articulation vertex, regardless of their edge choices.
Common mistake
(Counting the direct edge more than once)
An internally disjoint family is a set of distinct paths. The one-edge path has an empty interior, so it is disjoint from every other path, but it is still a single path: listing it twice does not raise the count. In the count is exactly , one direct edge and two-edge paths.
Common mistake
(Letting fan paths share a target)
A -fan to ends at distinct vertices of . Several internally disjoint paths from to one target express the local Menger property for the pair , which is a different statement. In the proof, it is the single auxiliary vertex , reached from by its final edges, that forces the truncated paths to end at different targets.
Common mistake
(Testing the converse on one target set)
The converse criterion needs a fan for every source and every -element target set. In the two triangles sharing , the center has the -fan and to the two other vertices of one triangle, yet the graph is not -connected. A source whose targets are all its neighbors certifies nothing about remote bottlenecks.
Summary
The global deletion definition is equivalent to disjoint paths for every pair once adjacent endpoints are handled by removing and restoring their edge. An auxiliary target vertex proves the fan lemma, and a carefully chosen target set proves its converse. Degree, vertex resilience and edge resilience remain different quantities with different certificates.
Exercises
Quick check
(Prove that deleting one vertex from a -connected graph leaves a -connected graph when .)
Check the remaining order and then quantify over further deletions.
Solution · Answer
After deleting , at least vertices remain, meeting the order requirement for -connectivity. If is any set of fewer than remaining vertices, then . The original graph's guarantee makes connected. This is exactly the deletion test for . The statement gives a lower bound, not an assertion that connectivity always drops by exactly one.
Quick check
(Prove that a wheel with at least three rim vertices has vertex connectivity exactly three, under the convention that a graph on vertices has connectivity at most .)
Separate the triangular rim from larger rims.
Solution · Answer
The worked proof gives three-connectivity for every permitted wheel. With a triangular rim the wheel is , whose order limits connectivity to three. With at least four rim vertices, each rim vertex has degree three. Deleting its three neighbors isolates it and leaves at least one other vertex, so connectivity is at most three. Combined with the established lower bound, it is exactly three in both cases.
Quick check
(For the two triangles sharing , determine both vertex connectivity and edge connectivity. Give deletion certificates and prove the required lower bounds.)
Edge connectivity here is the smallest number of edges whose deletion disconnects the connected graph.
Solution
The graph is connected and has at least two vertices, so its vertex connectivity is at least one. Deleting disconnects it, proving that value is exactly one.
Deleting any one edge breaks at most one triangle into a path; that path remains attached at to the other triangle, so the graph stays connected. Edge connectivity is therefore at least two. Deleting the two edges incident to any noncentral vertex isolates it while other vertices remain, giving an edge cut of size two. Hence edge connectivity is exactly two. This comparison identifies a genuine vertex bottleneck even though no edge alone is a bridge.