WHITNEY'S THEOREM — a graph is n-tuply connected iff any two points are joined by n disjoint paths
ProvedBalinski61.Whitney.whitney_theoremLet be a finite graph with at least two points and let be an integer. Then is -tuply connected (at least points, and connected after deleting any or fewer points) if and only if, for every pair of distinct points , there are disjoint paths from to — pairwise distinct simple paths no two of which share a point other than and :
This is Whitney's 1932 characterization of vertex connectivity (the vertex form of Menger's theorem). Balinski gives a proof of the "only if" direction from the max-flow min-cut theorem with point and line capacities, and combines it with his theorem on polytope graphs to obtain disjoint paths between any two vertices of a bounded full-dimensional polyhedron in -space.
Formalization Note The hypothesis is added: the paper's "any pair of points" presupposes two points, and without it the equivalence fails for a one-point graph and . Paths are required to be pairwise distinct and simple; see the definition file. No assumption is made: for both sides hold for every graph with at least one point.
import Mathlib import Definitions.Def_Balinski61_Whitney_Graph
namespace Balinski61.Whitney
theorem whitney_theorem {V : Type*} [Fintype V] (G : SimpleGraph V) (n : ℕ)
(hcard : 2 ≤ Fintype.card V) :
IsNTuplyConnected G n ↔ ∀ ps pk : V, ps ≠ pk → HasNDisjointPaths G n ps pk := by sorry
end Balinski61.Whitney
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.