digraph_is_two_linked
def
A digraph D is 2-linked if for every four pairwise distinct vertices s₁, t₁, s₂, t₂ in D, there exist vertex-disjoint directed paths from s₁ to t₁ and from s₂ to t₂.
Statement
def digraph_is_two_linked {V : Type*} (D : Digraph V) : Prop
- Defined in
- arXiv:2610.36895 Sec. 1
- Verified
- 28 Oct 2026
- Axioms
- none listed
- Built on 1
- digraph_is_directed_pathA directed path from u to v in a digraph D is a list of vertices p forming a directed chain in D with no duplicate vertices, starting at u…
- Used by 1
- digraph_unilaterally_two_linked_of_two_linkedEvery 2-linked digraph is unilaterally 2-linked.
Read back from the Lean
For a directed graph D on vertex type V, digraph_is_two_linked D asserts that for all vertices s₁, t₁, s₂, t₂ : V, if s₁, t₁, s₂, and t₂ are pairwise distinct (the list [s₁, t₁, s₂, t₂] has no duplicates), then there exist vertex lists p₁ and p₂ such that:
1. p₁ is a directed path in D from s₁ to t₁,
2. p₂ is a directed path in D from s₂ to t₂, and
3. p₁ and p₂ are disjoint (share no vertices).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- A digraph is 2-linked if every four distinct terminals have vertex-disjoint directed paths. -/ def digraph_is_two_linked {V : Type*} (D : Digraph V) : Prop := ∀ (s₁ t₁ s₂ t₂ : V), [s₁, t₁, s₂, t₂].Nodup → ∃ (p₁ p₂ : List V), digraph_is_directed_path D p₁ s₁ t₁ ∧ digraph_is_directed_path D p₂ s₂ t₂ ∧ p₁.Disjoint p₂