Lesson 4

Theorem (Menger, 1927). Let \(G(V,E)\) be an undirected or directed graph, and let \(s\) and \(t\) be two distinct vertices.

• Edge-connectivity.  The minimum number of edges that need to be removed so that no path remains from \(s\) to \(t\) equals the maximum number of edge-disjoint paths from \(s\) to \(t\). Thus, a graph is edge \(k\)-connected if and only if there are \(k\) edge-disjoint paths between any two vertices.


• Vertex-connectivity.  Assume that \((s,t) \not \in E\). The minimum number of vertices that need to be removed so that no path remains from \(s\) to \(t\) equals the maximum number of vertex-disjoint paths from \(s\) to \(t\). Thus, a graph is vertex \(k\)-connected if and only if there are \(k\) vertex-disjoint paths between any two vertices.