AFTD Auto-Formalizing Theoretical Domains

linkage_of_common_neighbor

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
    {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 op_620_four_strong_semicomplete_multipartite_unilaterally_two_linked
Verified
30 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • short_path_gives_linkage_four_strongIn a 4-strong digraph D, if there is a directed path between {s₁, t₁} with at most 3 vertices that avoids {s₂, t₂}, then there exist…
  • 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…
  • 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…
Used by 1
  • linkage_of_common_neighbor_rightIn 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₁,…

The proof, explained

The proof proceeds by case analysis on the direction of the 2-step path through the outside vertex $v$, either $s₁ \to v \to t₁$ or $t₁ \to v \to s₁$. In either case, the 3-vertex sequence forms a directed path between $s₁$ and $t₁$ of length 3 (consisting of 2 edges). Because $v \notin \{s₁, t₁, s₂, t₂\}$ and the terminal vertices are pairwise distinct, this short path avoids both $s₂$ and $t₂$. The theorem `short_path_gives_linkage_four_strong` then directly guarantees the existence of a unilateral 2-linkage in the 4-strong digraph.

  1. The distinctness assumption on $\{s₁, t₁, s₂, t₂\}$ and the condition $v \notin [s₁, t₁, s₂, t₂]$ are simplified into explicit pairwise disequalities.

    We make a copy of `hnodup` as `h_nodup_simped` and rewrite both `h_nodup_simped` and `hv` using `List.nodup_cons`, `List.mem_cons`, `List.not_mem_nil`, and `not_false_eq_true`. This unpacks the list-level assertions into propositional conjunctions of inequalities, making pairwise disequalities between $v$ and the terminal vertices $\{s₁, t₁, s₂, t₂\}$ readily available.

    lines 12–13

    uses List.nodup_cons, List.mem_cons, List.not_mem_nil, not_false_eq_true

      have h_nodup_simped := hnodup
      simp only [List.nodup_cons, List.mem_cons, List.not_mem_nil, not_false_eq_true] at h_nodup_simped hv
  2. In the forward case ($s₁ \to v$ and $v \to t₁$), the 3-vertex sequence $[s₁, v, t₁]$ is a directed path in $D$ from $s₁$ to $t₁$.

    We case split on `hdir`. In the first case, we have directed edges $s₁ \to v$ and $v \to t₁$. We construct `hpath` showing $[s₁, v, t₁]$ is a directed path: the chain condition holds by simplification with the two edge hypotheses; the absence of duplicates in $[s₁, v, t₁]$ reduces by `simp only` and is closed by propositional logic (`tauto`) from the pairwise disequalities; and the endpoints match $s₁$ and $t₁$ by reflexivity (`rfl`).

    lines 14–19

    uses List.nodup_cons, List.mem_cons, List.not_mem_nil, not_false_eq_true

      cases hdir with
      | inl h =>
        have hpath : digraph_is_directed_path D [s₁, v, t₁] s₁ t₁ := by
          refine ⟨by simp [h.1, h.2], ?_, rfl, rfl⟩
          simp only [List.nodup_cons, List.mem_cons, List.not_mem_nil, not_false_eq_true]
          tauto
  3. In the forward case ($s₁ \to v \to t₁$), the unilateral 2-linkage exists.

    We apply the lemma `short_path_gives_linkage_four_strong` with the path $[s₁, v, t₁]$. The path connects $s₁$ to $t₁$ via `Or.inl hpath`, has length 3 which satisfies the length requirement $3 \le 3$ by reflexivity (`le_rfl`), and avoids $s₂$ and $t₂$. Expanding the avoidance condition via `List.mem_cons` and `List.not_mem_nil`, propositional logic (`tauto`) verifies that neither $s₂$ nor $t₂$ coincides with any vertex in $[s₁, v, t₁]$, concluding this case.

    lines 20–22

    uses short_path_gives_linkage_four_strong, Or.inl, le_rfl, List.mem_cons, List.not_mem_nil

        apply short_path_gives_linkage_four_strong D hstrong hnodup [s₁, v, t₁] (Or.inl hpath) le_rfl
        simp only [List.mem_cons, List.not_mem_nil]
        tauto
  4. In the reverse case ($t₁ \to v$ and $v \to s₁$), the 3-vertex sequence $[t₁, v, s₁]$ is a directed path in $D$ from $t₁$ to $s₁$.

    In the second branch of `hdir`, we have directed edges $t₁ \to v$ and $v \to s₁$. Symmetrically to the first case, we construct `hpath` showing $[t₁, v, s₁]$ is a directed path from $t₁$ to $s₁$: the chain condition holds by the edge hypotheses, the endpoints are $t₁$ and $s₁$ by reflexivity, and the list has no duplicates by propositional logic (`tauto`) after expanding via `simp only`.

    lines 23–27

    uses List.nodup_cons, List.mem_cons, List.not_mem_nil, not_false_eq_true

      | inr h =>
        have hpath : digraph_is_directed_path D [t₁, v, s₁] t₁ s₁ := by
          refine ⟨by simp [h.1, h.2], ?_, rfl, rfl⟩
          simp only [List.nodup_cons, List.mem_cons, List.not_mem_nil, not_false_eq_true]
          tauto
  5. In the reverse case ($t₁ \to v \to s₁$), the unilateral 2-linkage exists, concluding the proof.

    We apply `short_path_gives_linkage_four_strong` with $[t₁, v, s₁]$ via `Or.inr hpath` and length bound $3 \le 3$ by `le_rfl`. After expanding list membership with `List.mem_cons` and `List.not_mem_nil`, propositional logic (`tauto`) confirms that $s₂$ and $t₂$ are distinct from $t₁, v, s₁$, completing the proof.

    lines 28–30

    uses short_path_gives_linkage_four_strong, Or.inr, le_rfl, List.mem_cons, List.not_mem_nil

        apply short_path_gives_linkage_four_strong D hstrong hnodup [t₁, v, s₁] (Or.inr hpath) le_rfl
        simp only [List.mem_cons, List.not_mem_nil]
        tauto
List.nodup_cons
A list $a :: l$ has no duplicate elements if and only if $a \notin l$ and $l$ has no duplicate elements.
List.mem_cons
An element $x$ belongs to $b :: l$ if and only if $x = b$ or $x \in l$.
List.not_mem_nil
No element belongs to the empty list.
not_false_eq_true
The negation of `False` is equal to `True`.
short_path_gives_linkage_four_strong
In a 4-strong digraph, if $\{s₁, t₁, s₂, t₂\}$ are pairwise distinct and there is a directed path between $s₁$ and $t₁$ (in either direction) of length at most 3 avoiding $s₂$ and $t₂$, then a unilateral 2-linkage exists for $\{s₁, t₁\}$ and $\{s₂, t₂\}$.
Or.inl
From a proof of $A$, infer the disjunction $A \vee B$.
Or.inr
From a proof of $B$, infer the disjunction $A \vee B$.
le_rfl
The preorder relation $\le$ is reflexive ($a \le a$).

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

/-- If an outside vertex forms a 2-step directed path between {s₁, t₁}, then unilateral 2-linkage exists in a 4-strong digraph. -/theorem linkage_of_common_neighbor    {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 h_nodup_simped := hnodup  simp only [List.nodup_cons, List.mem_cons, List.not_mem_nil, not_false_eq_true] at h_nodup_simped hv  cases hdir with  | inl h =>    have hpath : digraph_is_directed_path D [s₁, v, t₁] s₁ t₁ := by      refine ⟨by simp [h.1, h.2], ?_, rfl, rfl⟩      simp only [List.nodup_cons, List.mem_cons, List.not_mem_nil, not_false_eq_true]      tauto    apply short_path_gives_linkage_four_strong D hstrong hnodup [s₁, v, t₁] (Or.inl hpath) le_rfl    simp only [List.mem_cons, List.not_mem_nil]    tauto  | inr h =>    have hpath : digraph_is_directed_path D [t₁, v, s₁] t₁ s₁ := by      refine ⟨by simp [h.1, h.2], ?_, rfl, rfl⟩      simp only [List.nodup_cons, List.mem_cons, List.not_mem_nil, not_false_eq_true]      tauto    apply short_path_gives_linkage_four_strong D hstrong hnodup [t₁, v, s₁] (Or.inr hpath) le_rfl    simp only [List.mem_cons, List.not_mem_nil]    tauto
See it in the graphDiscuss this resultChallenge it