AFTD Auto-Formalizing Theoretical Domains

digraph_five_strong_short_path_avoiding_finset

theoremverified

Let D be 5-strong, A₀ a set of at most 2 vertices and T a set of fewer than 3 vertices. Then any two distinct vertices outside T ∪ A₀ are joined by a directed path avoiding T ∪ A₀. This is 5-strongness applied to the set T ∪ A₀, which has fewer than 5 vertices.

Statement

theorem digraph_five_strong_short_path_avoiding_finset {V : Type*} [Fintype V] [DecidableEq V]
    (D : Digraph V) (hstrong : digraph_is_k_strong D 5) (A₀ : Finset V) (hA : A₀.card ≤ 2)
    (T : Finset V) (hT : T.card < 3) {u v : V} (huT : u ∉ T) (hvT : v ∉ T)
    (huA : u ∉ A₀) (hvA : v ∉ A₀) (huv : u ≠ v) :
    ∃ p : List V, digraph_is_directed_path D p u v ∧ (∀ x ∈ p, x ∉ T) ∧ ∀ x ∈ p, x ∉ A₀
Source
step towards digraph_five_strong_co_bipartite_unilaterally_two_linked
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • 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

The proof applies the definition of 5-strong connectivity directly to the set T ∪ A₀. Since |T| < 3 and |A₀| ≤ 2, the union has size at most 4 < 5. Because u and v are distinct vertices outside T ∪ A₀, 5-strongness yields a directed path from u to v avoiding the union. Finally, avoiding T ∪ A₀ is decomposed into avoiding T and avoiding A₀ individually.

  1. |T ∪ A₀| < 5

    By Finset.card_union_le, |T ∪ A₀| ≤ |T| + |A₀|. Since |T| < 3 and |A₀| ≤ 2, their sum is at most 4, so linear arithmetic (omega) concludes that |T ∪ A₀| < 5.

    lines 7–9

    uses Finset.card_union_le

      have hcard : (T ∪ A₀).card < 5 := by
        have h := Finset.card_union_le T A₀
        omega
  2. u ∉ T ∪ A₀ and v ∉ T ∪ A₀

    Since u is assumed to belong to neither T nor A₀, it does not belong to their union. The exact same reasoning applies to v.

    lines 10–11

      have hu : u ∉ T ∪ A₀ := by simp [huT, huA]
      have hv : v ∉ T ∪ A₀ := by simp [hvT, hvA]
  3. There exists a directed path p from u to v avoiding T ∪ A₀.

    By definition, 5-strong connectivity (hstrong.2) guarantees that between any two distinct vertices avoiding a set of fewer than 5 vertices, there is a directed path avoiding that set. Applying this to T ∪ A₀ (size < 5) and distinct vertices u, v ∉ T ∪ A₀ produces such a path p.

    line 12

      obtain ⟨p, hp1, hp2⟩ := hstrong.2 (T ∪ A₀) hcard u v hu hv huv
  4. Every vertex on p lies in neither T nor A₀.

    For each vertex x ∈ p, we have x ∉ T ∪ A₀. Rewriting using Finset.notMem_union yields the conjunction x ∉ T ∧ x ∉ A₀.

    lines 13–15

    uses Finset.notMem_union

      have hp2' : ∀ x ∈ p, x ∉ T ∧ x ∉ A₀ := by
        intro x hx
        simpa [Finset.notMem_union] using hp2 x hx
  5. The path p satisfies all conditions of the theorem.

    We package p together with the proof that it is a directed path from u to v and the two separate avoidance conditions (x ∉ T and x ∉ A₀ for all x ∈ p) extracted from the conjunction.

    line 16

      exact ⟨p, hp1, fun x hx => (hp2' x hx).1, fun x hx => (hp2' x hx).2⟩
Finset.card_union_le
The cardinality of the union of two finite sets is at most the sum of their cardinalities.
Finset.notMem_union
An element does not belong to the union of two finite sets if and only if it belongs to neither set.

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

/-- Five-strongness, applied to T ∪ A₀, gives paths avoiding both T and a set A₀ of at most two vertices. -/theorem digraph_five_strong_short_path_avoiding_finset {V : Type*} [Fintype V] [DecidableEq V]    (D : Digraph V) (hstrong : digraph_is_k_strong D 5) (A₀ : Finset V) (hA : A₀.card ≤ 2)    (T : Finset V) (hT : T.card < 3) {u v : V} (huT : u ∉ T) (hvT : v ∉ T)    (huA : u ∉ A₀) (hvA : v ∉ A₀) (huv : u ≠ v) :    ∃ p : List V, digraph_is_directed_path D p u v ∧ (∀ x ∈ p, x ∉ T) ∧ ∀ x ∈ p, x ∉ A₀ := by  have hcard : (T ∪ A₀).card < 5 := by    have h := Finset.card_union_le T A₀    omega  have hu : u ∉ T ∪ A₀ := by simp [huT, huA]  have hv : v ∉ T ∪ A₀ := by simp [hvT, hvA]  obtain ⟨p, hp1, hp2⟩ := hstrong.2 (T ∪ A₀) hcard u v hu hv huv  have hp2' : ∀ x ∈ p, x ∉ T ∧ x ∉ A₀ := by    intro x hx    simpa [Finset.notMem_union] using hp2 x hx  exact ⟨p, hp1, fun x hx => (hp2' x hx).1, fun x hx => (hp2' x hx).2⟩
See it in the graphDiscuss this resultChallenge it