Vertex connectivity κ(G): minimum vertices to remove to disconnect G (or make trivial). Whitney's inequality: κ(G) ≤ λ(G) ≤ δ(G). Menger's theorem: κ equals max number of internally vertex-disjoint paths between any pair.
How to Use
Select graph:
- κ: Vertex connectivity
- Whitney: κ ≤ λ ≤ δ
- Menger: Disjoint paths
Menger's Theorem
The maximum number of internally vertex-disjoint u-v paths equals the minimum u-v vertex cut. This is the vertex version of max-flow min-cut. Menger (1927) proved both vertex and edge versions.
k-Connectivity
G is k-connected if κ(G) ≥ k: removing any k-1 vertices leaves G connected. 1-connected = connected. 2-connected = no cut vertex. 3-connected = no vertex pair whose removal disconnects. Planar 3-connected → unique embedding (Whitney).
Step-by-Step Instructions
- 1Select graph.
- 2Compute κ(G).
- 3Check Whitney.
- 4Find cut vertices.
- 5Determine k.