digraph_five_strong_short_path_avoiding_finset
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.
|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.
uses
Finset.card_union_lehave hcard : (T ∪ A₀).card < 5 := by have h := Finset.card_union_le T A₀ omega
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.
have hu : u ∉ T ∪ A₀ := by simp [huT, huA] have hv : v ∉ T ∪ A₀ := by simp [hvT, hvA]
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.
obtain ⟨p, hp1, hp2⟩ := hstrong.2 (T ∪ A₀) hcard u v hu hv huvEvery 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₀.
uses
Finset.notMem_unionhave hp2' : ∀ x ∈ p, x ∉ T ∧ x ∉ A₀ := by intro x hx simpa [Finset.notMem_union] using hp2 x hx
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.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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⟩