Menger's theorem

Remarks

In both parts, the inequality "at least" is easy: each separating set must contain a vertex or edge from each of the disjoint paths. The other inequality can be proved by induction on the number of edges. It also follows from the max-flow min-cut theorem, with capacity $1$ on each edge or each vertex and integral flows. In part 1 the hypothesis that $u$ and $v$ are not adjacent is needed: if $uv$ is an edge, no set of other vertices separates $u$ from $v$. For example, in the cycle $C_6$ two opposite vertices are joined by two internally disjoint paths, and removing one inner vertex from each of these paths separates them. A global form, due to Whitney, follows. A graph with more than $k$ vertices is $k$-vertex-connected if and only if every two distinct vertices are joined by $k$ internally disjoint paths.

Going deeper

For a student

Menger's theorem is the basic min-max theorem of graph connectivity. It turns the definition of $k$-connectivity, which is about removing vertices, into a statement about disjoint paths, which is often easier to use. It is a special case of max-flow min-cut, and it is equivalent in strength to Kőnig's theorem and Hall's marriage theorem on bipartite matchings.