AFTD Auto-Formalizing Theoretical Domains

digraph_unilaterally_two_linked_of_two_linked

theoremverified

Every 2-linked digraph is unilaterally 2-linked.

Statement

theorem digraph_unilaterally_two_linked_of_two_linked {V : Type*} (D : Digraph V)
    (h : digraph_is_two_linked D) : digraph_is_unilaterally_two_linked D
Source
arXiv:2610.36895 Sec. 1
Verified
29 Oct 2026
Axioms
none — Lean reports it depends on no axioms
Built on 3
  • digraph_is_two_linkedA 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…
  • digraph_is_unilaterally_two_linkedA digraph D is unilaterally 2-linked if for every four pairwise distinct vertices s₁, t₁, s₂, t₂ in D, there exist vertex-disjoint…
  • 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…

Read back from the Lean

For any type V and any directed graph D on V, if D is 2-linked, then D is unilaterally 2-linked. That is, if for every quadruple of pairwise distinct vertices $(s_1, t_1, s_2, t_2)$, there exist vertex-disjoint directed paths $p_1$ from $s_1$ to $t_1$ and $p_2$ from $s_2$ to $t_2$, then for every quadruple of pairwise distinct vertices $(s_1, t_1, s_2, t_2)$, there exist vertex-disjoint directed paths $p_1, p_2$ such that $p_1$ goes either from $s_1$ to $t_1$ or from $t_1$ to $s_1$, and $p_2$ goes either from $s_2$ to $t_2$ or from $t_2$ to $s_2$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

A digraph is unilaterally 2-linked if for any four distinct vertices s₁, t₁, s₂, t₂, there exist disjoint directed paths connecting s₁ with t₁ and s₂ with t₂, each in either direction. A 2-linked digraph satisfies the strictly stronger condition where the paths must be directed specifically from s₁ to t₁ and from s₂ to t₂. Thus, the disjoint paths guaranteed by 2-linkedness immediately witness unilateral 2-linkedness by taking the forward direction for each pair.

  1. Given four pairwise distinct vertices s₁, t₁, s₂, t₂, there exist vertex-disjoint directed paths p₁ from s₁ to t₁ and p₂ from s₂ to t₂.

    To show that D is unilaterally 2-linked, we consider arbitrary vertices s₁, t₁, s₂, t₂ that are pairwise distinct (line 4). By the hypothesis h that D is 2-linked, there exist directed paths p₁ from s₁ to t₁ and p₂ from s₂ to t₂ that are disjoint (line 5).

    lines 4–5

      intro s₁ t₁ s₂ t₂ hnd
      obtain ⟨p₁, p₂, hp₁, hp₂, hdisj⟩ := h s₁ t₁ s₂ t₂ hnd
  2. The paths p₁ and p₂ witness that D is unilaterally 2-linked.

    Unilateral 2-linkedness requires each pair of vertices to be connected by a directed path in at least one direction (either sᵢ → tᵢ or tᵢ → sᵢ). Since p₁ is directed from s₁ to t₁ and p₂ is directed from s₂ to t₂, both disjunctions are satisfied by choosing the forward direction via Or.inl. Together with the fact that p₁ and p₂ are disjoint, this completes the proof.

    line 6

    uses Or.inl

      exact ⟨p₁, p₂, Or.inl hp₁, Or.inl hp₂, hdisj⟩
Or.inl
from a proof of A, concludes the disjunction A ∨ B

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- Every 2-linked digraph is unilaterally 2-linked. -/theorem digraph_unilaterally_two_linked_of_two_linked {V : Type*} (D : Digraph V)    (h : digraph_is_two_linked D) : digraph_is_unilaterally_two_linked D := by  intro s₁ t₁ s₂ t₂ hnd  obtain ⟨p₁, p₂, hp₁, hp₂, hdisj⟩ := h s₁ t₁ s₂ t₂ hnd  exact ⟨p₁, p₂, Or.inl hp₁, Or.inl hp₂, hdisj⟩
See it in the graphDiscuss this resultChallenge it