Menger's theorem (set form)
ProvedMenger.menger_setMenger's theorem, set form. Let be a graph, a finite set of vertices, and . Suppose every – separator (a set meeting every – path inside ) has at least vertices. Then contains pairwise vertex-disjoint – paths inside :
Together with the trivial converse (a separator meets each path of a linkage) this says that the maximum number of disjoint – paths equals the minimum size of an – separator. The vertex form of Menger's theorem for two vertices, and Whitney's characterization of -connected graphs, follow from it.
Formalization Note Paths are duplicate-free lists of vertices, so a single vertex of is a path, and separators may contain vertices of . The set plays the role of the ambient graph ; taking to be the whole vertex set gives the usual statement.
import Mathlib import Definitions.Def_Menger_Linkage
namespace Menger
theorem menger_set {V : Type*} [DecidableEq V] (G : SimpleGraph V) (S A B : Finset V)
(hA : A ⊆ S) (hB : B ⊆ S) (k : ℕ)
(hsep : ∀ X : Finset V, X ⊆ S → IsABSep G S A B X → k ≤ X.card) :
HasLinkage G S A B k := by sorry
end Menger