AFTD Auto-Formalizing Theoretical Domains

digraph_is_unilaterally_two_linked

def

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

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