AFTD Auto-Formalizing Theoretical Domains

linkage_of_common_neighbor_right

theoremverified

In a 4-strong digraph D, if v is outside {s₁, t₁, s₂, t₂} and (s₂ → v → t₂) or (t₂ → v → s₂), then unilateral 2-linkage exists for {s₁, t₁} and {s₂, t₂}.

Statement

theorem linkage_of_common_neighbor_right
    {V : Type*} [Fintype V] (D : Digraph V)
    (hstrong : digraph_is_k_strong D 4)
    {s₁ t₁ s₂ t₂ : V} (hnodup : [s₁, t₁, s₂, t₂].Nodup)
    (v : V) (hv : v ∉ [s₁, t₁, s₂, t₂])
    (hdir : (D.Adj s₂ v ∧ D.Adj v t₂) ∨ (D.Adj t₂ v ∧ D.Adj v s₂)) :
    ∃ (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₂
Source
step towards digraph_four_strong_semicomplete_multipartite_nonadjacent_pairs_linked
Verified
01 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • linkage_of_common_neighborIn a 4-strong digraph D, if v is outside {s₁, t₁, s₂, t₂} and (s₁ → v → t₁) or (t₁ → v → s₁), then unilateral 2-linkage exists for {s₁,…
  • digraph_is_k_strongA finite digraph D is k-strong (k-strongly connected) if its vertex count exceeds k and for every vertex subset s of cardinality strictly…
  • 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…

The proof, explained

This theorem is the symmetric analogue of `linkage_of_common_neighbor`, addressing the case where the intermediate vertex v forms a 2-step directed path with the second terminal pair {s₂, t₂} rather than the first. The proof swaps the order of the terminal pairs to (s₂, t₂, s₁, t₁), checks that distinctness and disjointness from v still hold, applies `linkage_of_common_neighbor`, and finally swaps the resulting paths back to the original order.

  1. The reordered list of terminal vertices [s₂, t₂, s₁, t₁] contains no duplicates.

    We expand the duplicate-free condition into pairwise inequalities across the list elements using `simp only` with basic list lemmas (`List.nodup_cons`, `List.mem_cons`, `List.not_mem_nil`, `or_false`, `List.nodup_nil`, `and_true`). Since the original list [s₁, t₁, s₂, t₂] is duplicate-free (`hnodup`), propositional logic and symmetry of equality (`tauto`) verify that the permuted list [s₂, t₂, s₁, t₁] also has distinct entries.

    lines 12–15

    uses List.nodup_cons, List.mem_cons, List.not_mem_nil, or_false, List.nodup_nil, and_true

      have hnodup' : [s₂, t₂, s₁, t₁].Nodup := by
        simp only [List.nodup_cons, List.mem_cons, List.not_mem_nil, or_false,
          List.nodup_nil, and_true] at hnodup ⊢
        tauto
  2. The vertex v does not belong to [s₂, t₂, s₁, t₁].

    Rewriting list membership into disjunctions of equalities using `List.mem_cons` and `List.not_mem_nil` allows propositional logic (`tauto`) to deduce v ∉ [s₂, t₂, s₁, t₁] from the hypothesis v ∉ [s₁, t₁, s₂, t₂].

    lines 16–18

    uses List.mem_cons, List.not_mem_nil

      have hv' : v ∉ [s₂, t₂, s₁, t₁] := by
        simp only [List.mem_cons, List.not_mem_nil] at hv ⊢
        tauto
  3. There exist disjoint directed paths p₁ and p₂ such that p₁ unilaterally connects {s₂, t₂} and p₂ unilaterally connects {s₁, t₁}.

    We invoke `linkage_of_common_neighbor` with the terminal pairs swapped, using the 4-connectivity of D, the duplicate-free list [s₂, t₂, s₁, t₁], the fact that v avoids these terminals, and the assumption `hdir` that v provides a directed 2-step path between s₂ and t₂. This produces two vertex-disjoint paths: p₁ connecting {s₂, t₂} and p₂ connecting {s₁, t₁}.

    lines 19–20

    uses linkage_of_common_neighbor

      obtain ⟨p₁, p₂, ⟨h₁, h₂, hd⟩⟩ :=
        linkage_of_common_neighbor D hstrong hnodup' v hv' hdir
  4. The pair (p₂, p₁) witnesses the existence of a unilateral 2-linkage for {s₁, t₁} and {s₂, t₂}.

    We provide p₂ as the path between {s₁, t₁} and p₁ as the path between {s₂, t₂}. Their disjointness is immediate from the disjointness of p₁ and p₂ by the symmetry of disjoint lists.

    line 21

      exact ⟨p₂, p₁, h₂, h₁, hd.symm⟩
List.nodup_cons
A non-empty list `a :: l` has no duplicates if and only if `a ∉ l` and `l` has no duplicates.
List.mem_cons
An element belongs to `b :: l` if and only if it equals `b` or belongs to `l`.
List.not_mem_nil
The empty list contains no elements.
or_false
Disjunction of any proposition with `False` simplifies to the proposition itself.
List.nodup_nil
The empty list has no duplicate elements.
and_true
Conjunction of any proposition with `True` simplifies to the proposition itself.
linkage_of_common_neighbor
In a 4-strong digraph, if an external vertex forms a 2-step directed path with the first terminal pair, there exist disjoint unilateral paths connecting the first pair and the second pair.

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

/-- In a 4-strong digraph D, if v is outside {s₁, t₁, s₂, t₂} and (s₂ → v → t₂) or (t₂ → v → s₂), then unilateral 2-linkage exists for {s₁, t₁} and {s₂, t₂}. -/theorem linkage_of_common_neighbor_right    {V : Type*} [Fintype V] (D : Digraph V)    (hstrong : digraph_is_k_strong D 4)    {s₁ t₁ s₂ t₂ : V} (hnodup : [s₁, t₁, s₂, t₂].Nodup)    (v : V) (hv : v ∉ [s₁, t₁, s₂, t₂])    (hdir : (D.Adj s₂ v ∧ D.Adj v t₂) ∨ (D.Adj t₂ v ∧ D.Adj v s₂)) :    ∃ (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₂ := by  have hnodup' : [s₂, t₂, s₁, t₁].Nodup := by    simp only [List.nodup_cons, List.mem_cons, List.not_mem_nil, or_false,      List.nodup_nil, and_true] at hnodup ⊢    tauto  have hv' : v ∉ [s₂, t₂, s₁, t₁] := by    simp only [List.mem_cons, List.not_mem_nil] at hv ⊢    tauto  obtain ⟨p₁, p₂, ⟨h₁, h₂, hd⟩⟩ :=    linkage_of_common_neighbor D hstrong hnodup' v hv' hdir  exact ⟨p₂, p₁, h₂, h₁, hd.symm⟩
See it in the graphDiscuss this resultChallenge it