AFTD Auto-Formalizing Theoretical Domains

digraph_four_strong_semicomplete_multipartite_adjacent_pair_linked

theoremverifiedoriginal

Let D be a 4-strong semicomplete multipartite digraph on a finite type V. If s₁, t₁, s₂, t₂ are pairwise distinct vertices of D such that there is an arc between s₁ and t₁ in either direction, then there exist vertex-disjoint directed paths p₁ and p₂ where p₁ connects {s₁, t₁} and p₂ connects {s₂, t₂} in either direction.

Statement

theorem digraph_four_strong_semicomplete_multipartite_adjacent_pair_linked
    {V : Type*} [Fintype V] (D : Digraph V)
    (hstrong : digraph_is_k_strong D 4)
    (hmulti : digraph_is_semicomplete_multipartite D)
    {s₁ t₁ s₂ t₂ : V} (hnodup : [s₁, t₁, s₂, t₂].Nodup)
    (hadj : D.Adj s₁ t₁ ∨ D.Adj t₁ 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₂
Related work
arXiv:2610.36895 Sec. 5
Verified
30 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • 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_semicomplete_multipartiteA digraph D is semicomplete multipartite if it is loopless and its underlying inclusive simple graph has transitive non-adjacency (i.e.,…
  • 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

Let V be a finite type and D be a directed graph on V. Assume: 1. D is 4-strongly connected (digraph_is_k_strong D 4). 2. D is semicomplete multipartite (digraph_is_semicomplete_multipartite D). 3. s₁, t₁, s₂, t₂ are pairwise distinct vertices in V ([s₁, t₁, s₂, t₂].Nodup). 4. s₁ and t₁ are adjacent in D in at least one direction (D.Adj s₁ t₁ ∨ D.Adj t₁ s₁). Then there exist lists of vertices p₁ and p₂ in V such that: 1. p₁ is a simple directed path in D either from s₁ to t₁ or from t₁ to s₁, 2. p₂ is a simple directed path in D either from s₂ to t₂ or from t₂ to s₂, and 3. p₁ and p₂ are vertex-disjoint (p₁.Disjoint p₂).

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

Because s₁ and t₁ are adjacent, the single arc between them already forms a 2-vertex directed path p₁ connecting {s₁, t₁}. In a 4-strong digraph, deleting fewer than 4 vertices preserves strong connectivity; hence deleting the 2-element set {s₁, t₁} leaves a directed path p₂ between s₂ and t₂. By construction, p₂ completely avoids {s₁, t₁}, which immediately guarantees that p₁ and p₂ are vertex-disjoint.

  1. The four terminal vertices s₁, t₁, s₂, t₂ are pairwise distinct.

    Because the list [s₁, t₁, s₂, t₂] contains no duplicates by assumption, equating any pair among them produces an immediate contradiction. Each pairwise inequality (s₁ ≠ t₁, s₂ ≠ s₁, s₂ ≠ t₁, t₂ ≠ s₁, t₂ ≠ t₁, and s₂ ≠ t₂) is established by assuming equality and simplifying the no-duplicates hypothesis.

    lines 12–35

      classical
      have h11 : s₁ ≠ t₁ := by
        intro heq
        simp [heq] at hnodup
      have h21 : s₂ ≠ s₁ := by
        intro heq
        subst s₂
        simp at hnodup
      have h2t1 : s₂ ≠ t₁ := by
        intro heq
        subst s₂
        simp at hnodup
      have h3s1 : t₂ ≠ s₁ := by
        intro heq
        subst t₂
        simp at hnodup
      have h3t1 : t₂ ≠ t₁ := by
        intro heq
        subst t₂
        simp at hnodup
      have h22 : s₂ ≠ t₂ := by
        intro heq
        subst s₂
        simp at hnodup
  2. The obstacle set s = {s₁, t₁} has cardinality 2 < 4, and neither s₂ nor t₂ belongs to s.

    Since s₁ ≠ t₁, the finset s = {s₁, t₁} has cardinality 2 by Finset.card_pair, so |s| < 4. Furthermore, by expanding set membership with Finset.mem_insert, Finset.mem_singleton, and not_or, s₂ ∉ s and t₂ ∉ s follow from the distinctness of the terminals.

    lines 36–47

    uses Finset.card_pair, Finset.mem_insert, Finset.mem_singleton, not_or

      let s : Finset V := {s₁, t₁}
      have hcard : s.card < 4 := by
        have hc : s.card = 2 := by
          dsimp [s]
          exact Finset.card_pair h11
        omega
      have hs2 : s₂ ∉ s := by
        simp only [s, Finset.mem_insert, Finset.mem_singleton, not_or]
        exact ⟨h21, h2t1⟩
      have ht2 : t₂ ∉ s := by
        simp only [s, Finset.mem_insert, Finset.mem_singleton, not_or]
        exact ⟨h3s1, h3t1⟩
  3. There exists a directed path p₂ from s₂ to t₂ avoiding all vertices of s = {s₁, t₁}.

    By definition of a 4-strong digraph, removing any subset of strictly fewer than 4 vertices leaves a directed path between any two remaining distinct vertices. Applying this to the 2-element set s = {s₁, t₁} and the vertices s₂, t₂ ∉ s with s₂ ≠ t₂ yields a directed path p₂ from s₂ to t₂ whose vertices are all disjoint from s.

    line 48

      obtain ⟨p₂, hp₂path, hp₂avoid⟩ := hstrong.2 s hcard s₂ t₂ hs2 ht2 h22
  4. Any directed arc between distinct vertices forms a 2-vertex directed path.

    If there is an arc from u to v, then u ≠ v because semicomplete multipartite digraphs have no self-loops. Unfolding the definition of a directed path, the list [u, v] has distinct vertices, starts at u, ends at v, and consists of the single valid directed step u → v.

    lines 49–55

      have path_of_adj : ∀ {u v : V}, D.Adj u v → digraph_is_directed_path D [u, v] u v := by
        intro u v huv
        have hne : u ≠ v := by
          rintro rfl
          exact hmulti.1 u huv
        unfold digraph_is_directed_path
        simp [huv, hne]
  5. Both s₁ and t₁ belong to s.

    By definition of the set s = {s₁, t₁}, both endpoints s₁ and t₁ are members of s.

    lines 56–57

      have hs1mem : s₁ ∈ s := by simp [s]
      have ht1mem : t₁ ∈ s := by simp [s]
  6. If there is an arc from s₁ to t₁, the paths p₁ = [s₁, t₁] and p₂ are vertex-disjoint directed paths connecting the respective pairs.

    In the forward case where D.Adj s₁ t₁, the 2-vertex list p₁ = [s₁, t₁] is a directed path from s₁ to t₁. Any vertex in p₁ is either s₁ or t₁, both of which belong to s; since p₂ was constructed to avoid every element of s, no vertex of p₁ can appear in p₂, ensuring that p₁ and p₂ are disjoint.

    lines 58–66

    uses Or.inl, List.mem_cons, List.not_mem_nil, or_false

      rcases hadj with hst | hts
      · refine ⟨[s₁, t₁], p₂, Or.inl (path_of_adj hst), Or.inl hp₂path, ?_⟩
        intro a ha hb
        simp only [List.mem_cons, List.not_mem_nil, or_false] at ha
        rcases ha with h | h
        · rw [h] at hb
          exact (hp₂avoid s₁ hb) hs1mem
        · rw [h] at hb
          exact (hp₂avoid t₁ hb) ht1mem
  7. If there is an arc from t₁ to s₁, the paths p₁ = [t₁, s₁] and p₂ are vertex-disjoint directed paths connecting the respective pairs.

    Symmetrically, in the reverse case where D.Adj t₁ s₁, p₁ = [t₁, s₁] is a directed path from t₁ to s₁. Its vertices t₁ and s₁ are members of s, so disjointness with p₂ again follows from p₂ avoiding all vertices of s.

    lines 67–74

    uses Or.inr, Or.inl, List.mem_cons, List.not_mem_nil, or_false

      · refine ⟨[t₁, s₁], p₂, Or.inr (path_of_adj hts), Or.inl hp₂path, ?_⟩
        intro a ha hb
        simp only [List.mem_cons, List.not_mem_nil, or_false] at ha
        rcases ha with h | h
        · rw [h] at hb
          exact (hp₂avoid t₁ hb) ht1mem
        · rw [h] at hb
          exact (hp₂avoid s₁ hb) hs1mem
Finset.card_pair
A finite set consisting of two distinct elements has cardinality 2.
Finset.mem_insert
An element belongs to insert b s if and only if it equals b or belongs to s.
Finset.mem_singleton
An element belongs to the singleton {a} if and only if it equals a.
not_or
The negation of a disjunction ¬(p ∨ q) is equivalent to ¬p ∧ ¬q (De Morgan's law).
Or.inl
Constructs a proof of a disjunction a ∨ b from a proof of the left disjunct a.
Or.inr
Constructs a proof of a disjunction a ∨ b from a proof of the right disjunct b.
List.mem_cons
An element belongs to a cons list b :: l if and only if it equals b or belongs to l.
List.not_mem_nil
The empty list has no elements.
or_false
Disjunction with False simplifies to the proposition itself: (p ∨ False) ↔ p.

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 semicomplete multipartite digraph, any two pairs of distinct terminals with one pair adjacent in either direction admit vertex-disjoint paths. -/theorem digraph_four_strong_semicomplete_multipartite_adjacent_pair_linked    {V : Type*} [Fintype V] (D : Digraph V)    (hstrong : digraph_is_k_strong D 4)    (hmulti : digraph_is_semicomplete_multipartite D)    {s₁ t₁ s₂ t₂ : V} (hnodup : [s₁, t₁, s₂, t₂].Nodup)    (hadj : D.Adj s₁ t₁ ∨ D.Adj t₁ 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  classical  have h11 : s₁ ≠ t₁ := by    intro heq    simp [heq] at hnodup  have h21 : s₂ ≠ s₁ := by    intro heq    subst s₂    simp at hnodup  have h2t1 : s₂ ≠ t₁ := by    intro heq    subst s₂    simp at hnodup  have h3s1 : t₂ ≠ s₁ := by    intro heq    subst t₂    simp at hnodup  have h3t1 : t₂ ≠ t₁ := by    intro heq    subst t₂    simp at hnodup  have h22 : s₂ ≠ t₂ := by    intro heq    subst s₂    simp at hnodup  let s : Finset V := {s₁, t₁}  have hcard : s.card < 4 := by    have hc : s.card = 2 := by      dsimp [s]      exact Finset.card_pair h11    omega  have hs2 : s₂ ∉ s := by    simp only [s, Finset.mem_insert, Finset.mem_singleton, not_or]    exact ⟨h21, h2t1⟩  have ht2 : t₂ ∉ s := by    simp only [s, Finset.mem_insert, Finset.mem_singleton, not_or]    exact ⟨h3s1, h3t1⟩  obtain ⟨p₂, hp₂path, hp₂avoid⟩ := hstrong.2 s hcard s₂ t₂ hs2 ht2 h22  have path_of_adj : ∀ {u v : V}, D.Adj u v → digraph_is_directed_path D [u, v] u v := by    intro u v huv    have hne : u ≠ v := by      rintro rfl      exact hmulti.1 u huv    unfold digraph_is_directed_path    simp [huv, hne]  have hs1mem : s₁ ∈ s := by simp [s]  have ht1mem : t₁ ∈ s := by simp [s]  rcases hadj with hst | hts  · refine ⟨[s₁, t₁], p₂, Or.inl (path_of_adj hst), Or.inl hp₂path, ?_⟩    intro a ha hb    simp only [List.mem_cons, List.not_mem_nil, or_false] at ha    rcases ha with h | h    · rw [h] at hb      exact (hp₂avoid s₁ hb) hs1mem    · rw [h] at hb      exact (hp₂avoid t₁ hb) ht1mem  · refine ⟨[t₁, s₁], p₂, Or.inr (path_of_adj hts), Or.inl hp₂path, ?_⟩    intro a ha hb    simp only [List.mem_cons, List.not_mem_nil, or_false] at ha    rcases ha with h | h    · rw [h] at hb      exact (hp₂avoid t₁ hb) ht1mem    · rw [h] at hb      exact (hp₂avoid s₁ hb) hs1mem
See it in the graphDiscuss this resultChallenge it