Turn disjoint paths into a cut problem

Try

Two routes can be edge-disjoint while sharing an intermediate junction. If that junction fails, both routes fail together. Vertex-disjoint paths model a stronger form of redundancy: apart from the common endpoints, no vertex is shared. Menger’s theorem equates the maximum number of such paths with the minimum number of intermediate vertices whose deletion separates the endpoints.

Predict

Predict why adjacent endpoints need special handling. A direct edge from s to t cannot be destroyed by deleting other vertices, so there is no internal-vertex separator. We state the theorem for distinct nonadjacent vertices in a finite undirected graph. An already disconnected pair has both values zero. These boundary conditions prevent a superficially plausible formula from having an undefined right-hand side.

Experiment

For opposite vertices of a four-cycle, compare paths and cuts.

Object	Certificate	Size
Internally disjoint paths	The two arcs of the cycle	2
Internal separator	The other two vertices	2

One deleted intermediate vertex leaves the other arc. The equal-size certificates prove optimality without trying every path family. Contrast this with two triangles joined at one cut vertex, where that single junction limits redundancy across the join.

Understand

Reduce the problem to an integral flow network. Split every vertex v other than s, t into v_in and v_out joined by a directed edge of capacity one. Replace each undirected graph edge by directed arcs connecting the appropriate outgoing and incoming copies in both directions, using capacity M=n+1. Leave s, t unsplit. Internally vertex-disjoint paths give an integer flow by sending one unit along each route. Conversely any integer flow can be decomposed into unit s-t paths and cycles; remove cycles and simplify repeated vertices. Capacity one on each split edge ensures that the extracted paths share no internal vertex.

Apply

A separator of k internal vertices gives a cut of capacity at most k in the split network by deleting their unit edges and taking the source-reachable side. Since s, t are nonadjacent, deleting all n−2 internal vertices separates them, so the minimum cut has capacity at most n−2. It therefore cannot contain an edge of capacity M. A minimum cut consists only of unit split edges; the corresponding original vertices meet every s-t path and form a separator. Integral max-flow/min-cut now proves equality between the maximum disjoint-path count and the minimum separator size. The proof depends on the integral-flow theorem established immediately before this lesson.

Continue

For edge-disjoint paths, put capacity one on edges instead of splitting vertices and use the edge-cut version. In an undirected graph, opposite directed flows on the same edge can be canceled before decomposing, preserving value and ensuring an undirected capacity interpretation. Global vertex connectivity minimizes separator size across the graph, with complete graphs requiring the standard convention n−1. Do not conflate this global invariant with the endpoint-specific theorem proved here. In a resilience report, specify whether failures remove edges or vertices and present both a route family and a matching-size obstruction when possible.

Return to the combinatorics and graph theory unit for prerequisite choices and targeted retries. Continue with find a matching or a hall obstruction.