Directed edge-Menger theorem in edge-deletion form
ProvedDirKECC1549.Main.edge_menger_avoiddirected-graphsedge-connectivitymengers-theorem
Let be a finite directed multigraph, vertices, and . Then contains pairwise edge-disjoint directed trails from to if and only if, after deleting any set of fewer than edges, there remains a directed walk from to :
This is the directed edge form of Menger’s theorem, expressed in terms of resilience to edge deletion. Distinct edge identifiers account for parallel edges, and loops are allowed. If , the empty walk and arbitrarily many empty trails satisfy both sides; if , both sides hold vacuously.
Preamble
import Definitions.Def_DirKECC1549_Main_Graph set_option autoImplicit false
Formal statement
namespace DirKECC1549.Main
theorem edge_menger_avoid {n m : ℕ} (D : Fin m → Fin n × Fin n) (k : ℕ)
(x y : Fin n) : HasDisjointPaths D k x y ↔
∀ F : Finset (Fin m), F.card < k → ∃ p, IsWalk D x p y ∧
∀ e ∈ p, e ∉ F := by sorry
end DirKECC1549.Main
Source
Directed edge-Menger theorem, EPFL Graph Theory lecture notes, Lecture 9, Section 1, https://www.epfl.ch/labs/disopt/wp-content/uploads/2019/11/GT19_notes_to_date.pdf ; also Georgiadis et al., STOC 2027 submission #1549, Section 2 p.9. This is an edge-deletion formulation for the mission's graph encoding.