A graph is a k-connected graph if it has at least vertices and deleting any set of fewer than vertices, together with their incident edges, leaves a connected graph.
The vertex connectivity is the largest such . Equivalently, for a graph with at least two vertices, it is the smallest number of vertices whose deletion either disconnects the graph or leaves a single vertex. The latter convention gives for a complete graph. A disconnected graph has vertex connectivity zero; one usually also sets .
For distinct nonadjacent vertices , the local connectivity isSuch a set is an – vertex separator. By Menger's theorem, local connectivity also equals the maximum number of internally vertex-disjoint paths from to . If no graph path exists already, the empty vertex separator gives zero.
Past exam of the mathematics course of the University of Cambridge 2020 ii Paper 2 17G i Solution Created 2026-09-24 Updated 2026-09-29
For nonadjacent vertices , the local connectivity is the minimum cardinality of an - vertex separator: a set such that and lie in different components of .
To prove the vertex form of the Menger theorem, replace every vertex by an arc of capacity one. Replace every undirected edge by directed arcs from to and conversely, each of capacity larger than ; leave unsplit. An integral - flow of value decomposes into paths, and the unit-capacity vertex arcs force the corresponding graph paths to be internally vertex-disjoint paths. Conversely, such paths give an integral flow of value .
Because and are nonadjacent, any finite minimum cut consists entirely of unit-capacity vertex arcs. These arcs correspond exactly to an - vertex separator of the same size. The max-flow min-cut theorem, whose augmenting-path proof also guarantees an integral maximum flow for integral capacities, therefore givesIn particular, contains the required set of paths.