Paths, separators and linkages for Menger's theorem
DefinitionMenger_Linkageconnectivitygraph-theorymenger
Let be a graph and finite sets of vertices. An – path inside is a nonempty list of distinct vertices of , consecutive entries adjacent in , whose first vertex is in and whose last vertex is in (a single vertex of is allowed). A set of vertices is an – separator inside if every – path inside contains a vertex of . A linkage of size is a family of pairwise vertex-disjoint – paths inside . These notions are the data of the set form of Menger's theorem: the maximum size of a linkage equals the minimum size of a separator.
Definition code
import Mathlib
namespace Menger
variable {V : Type*}
/-- A path of `G` inside the vertex set `S`, listed from a vertex of `A` to a vertex of `B`: a
nonempty duplicate-free list of vertices of `S`, consecutive entries adjacent, whose first entry
lies in `A` and whose last entry lies in `B`. -/
def IsABPath (G : SimpleGraph V) (S A B : Finset V) (p : List V) : Prop :=
p ≠ [] ∧ p.Nodup ∧ List.IsChain G.Adj p ∧ (∀ v ∈ p, v ∈ S) ∧
(∃ a, p.head? = some a ∧ a ∈ A) ∧ (∃ b, p.getLast? = some b ∧ b ∈ B)
/-- `X` is an `A`–`B` separator inside `S`: it meets every `A`–`B` path of `G` inside `S`. -/
def IsABSep (G : SimpleGraph V) (S A B X : Finset V) : Prop :=
∀ p, IsABPath G S A B p → ∃ x ∈ X, x ∈ p
/-- There are `k` pairwise vertex-disjoint `A`–`B` paths of `G` inside `S`. -/
def HasLinkage (G : SimpleGraph V) (S A B : Finset V) (k : ℕ) : Prop :=
∃ L : List (List V), L.length = k ∧ (∀ p ∈ L, IsABPath G S A B p) ∧
L.Pairwise (fun p q => ∀ v ∈ p, v ∉ q)
end Menger
Source
R. Diestel, Graph Theory, 5th ed., Section 3.3, Theorem 3.3.1 (Menger 1927) and the definitions preceding it.
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.