digraph_is_unilaterally_two_linked
A digraph D is unilaterally 2-linked if for every four pairwise distinct vertices s₁, t₁, s₂, t₂ in D, there exist vertex-disjoint directed paths P₁ and P₂ such that P₁ connects {s₁, t₁} (in either direction) and P₂ connects {s₂, t₂} (in either direction).
Statement
def digraph_is_unilaterally_two_linked {V : Type*} (D : Digraph V) : Prop
- Defined in
- arXiv:2610.36895 Definition 1.1 and 2.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 3
- digraph_four_strong_tournament_unilaterally_two_linkedLet D be a digraph on a finite type V. If D is a tournament and D is 4-strong, then D is unilaterally 2-linked.
- digraph_exists_four_strong_semicomplete_multipartite_not_unilaterally_two_linked_eightThere exists a finite type V with exactly 8 elements and a digraph D on V such that D is 4-strong, semicomplete multipartite, and not…
- digraph_unilaterally_two_linked_of_two_linkedEvery 2-linked digraph is unilaterally 2-linked.
Read back from the Lean
A directed graph D on vertex type V is defined to be "unilaterally two-linked" if for all vertices s₁, t₁, s₂, t₂ : V, if the four vertices are pairwise distinct (i.e., [s₁, t₁, s₂, t₂].Nodup), then there exist two lists of vertices p₁, p₂ : List V such that:
1. p₁ is a directed path in D from s₁ to t₁, or from t₁ to s₁,
2. p₂ is a directed path in D from s₂ to t₂, or from t₂ to s₂, and
3. p₁ and p₂ are disjoint (i.e., 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 unilaterally 2-linked if every four distinct terminals have vertex-disjoint paths in some orientation. -/ def digraph_is_unilaterally_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₁ t₁ s₁) ∧ (digraph_is_directed_path D p₂ s₂ t₂ ∨ digraph_is_directed_path D p₂ t₂ s₂) ∧ p₁.Disjoint p₂