Vertex & Edge Connectivity

We formalize connectivity with two measures: vertex connectivity $\kappa(G)$ and edge connectivity $\lambda(G)$ . Menger's theorem beautifully connects these to disjoint paths, and Whitney's inequality relates $\kappa$ , $\lambda$ , and $\delta$ .

Learning Objectives

Define vertex connectivity κ(G) and edge connectivity λ(G)

State and apply Menger's theorem (vertex and edge versions)

Prove Whitney's inequality: κ(G) ≤ λ(G) ≤ δ(G)

Apply connectivity concepts to network reliability

Key Concepts

Vertex & Edge Connectivity

The vertex connectivity $\kappa(G)$ is the minimum number of vertices whose removal disconnects $G$ (or makes it trivial). The edge connectivity $\lambda(G)$ is the minimum number of edges whose removal disconnects $G$ .

-
$\kappa(G) \leq \lambda(G) \leq \delta(G)$
-
A graph is $k$ -connected if $\kappa(G) \geq k$
-
A graph is $k$ -edge-connected if $\lambda(G) \geq k$

Menger's Theorem

Menger's theorem connects connectivity to disjoint paths. Both directed and undirected versions hold:

-Edge version: The max number of edge-disjoint $s$ - $t$ paths equals the min edge cut separating $s$ from $t$ .
-Vertex version: The max number of internally vertex-disjoint $s$ - $t$ paths equals the min vertex cut separating $s$ from $t$ .

All four combinations (directed/undirected × edge/vertex) are proved via Max Flow-Min Cut.

-
Edge version (directed): unit-capacity network, apply Ford-Fulkerson
-
Edge version (undirected): replace each edge with two directed edges of capacity 1
-
Vertex version: split $v$ into $v_{in}, v_{out}$ with capacity 1, reducing to edge version
-
Global form: $G$ is $k$ -edge-connected $\iff$ there are $k$ edge-disjoint paths between every pair of vertices
-
Global form: $G$ is $k$ -connected $\iff$ there are $k$ internally vertex-disjoint paths between every pair of vertices

W10: Max Flow-Min Cut & Ford-Fulkerson W12: Dijkstra & Bellman-Ford