AFTD Auto-Formalizing Theoretical Domains

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

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₂
See it in the graphDiscuss this resultChallenge it