Vertex Connectivity
You'll learn how to measure a graph's resilience to vertex removal and what makes a graph k-connected.
What Is Vertex Connectivity?
Vertex connectivity measures how "robust" a graph is—specifically, how many vertices you must remove to disconnect it (or reduce it to a single vertex). It tells us the minimum number of vertices whose removal would break the graph into separate pieces.
Think of a communication network: vertex connectivity tells you the minimum number of nodes that must fail before the network splits into isolated groups. A higher vertex connectivity means a more reliable, fault-tolerant network.
Formal Definition
The vertex connectivity (denoted κ(G)) of a connected graph G is the minimum number of vertices that must be removed to either:
- Disconnect the graph, or
- Reduce it to a single vertex (for complete graphs)
A graph is called k-connected if its vertex connectivity is at least k. In other words, you need to remove at least k vertices to disconnect it.
Minimum Vertex Cuts
A vertex cut (or separating set) is a set of vertices whose removal increases the number of connected components. The smallest such set is a minimum vertex cut, and its size equals κ(G).
Example: In a graph that's a simple path (v₁—v₂—v₃—v₄), removing just v₂ or v₃ disconnects it, so κ(G) = 1.
Graph Robustness
- κ(G) = 0: Graph is disconnected (or has only one vertex)
- κ(G) = 1: Graph has at least one cut vertex
- κ(G) ≥ 2: Graph is 2-connected; no single vertex failure breaks it
- Higher κ means greater robustness
Key Takeaway: Vertex connectivity κ(G) is the size of the smallest vertex cut, measuring how many vertices must fail to disconnect a graph; a graph is k-connected if κ(G) ≥ k.