digraph_four_cycles_from_undominated_triangle
If a finite digraph of minimum outdegree at least seven has a directed triangle that no outside vertex dominates and the displayed three-cycle condition holds on induced subsets, then it has four pairwise vertex-disjoint directed cycles.
Statement
theorem digraph_four_cycles_from_undominated_triangle (α : Type) [Fintype α] [DecidableEq α] [Nonempty α] (D : Digraph α) [DecidableRel D.Adj] (hdeg : ∀ v, 7 ≤ (Finset.univ.filter fun w => D.Adj v w).card) (hthree : ∀ T : Finset α, T.Nonempty → (∀ v ∈ T, 5 ≤ (T.filter fun w => D.Adj v w).card) → ∃ s : Fin 3 → Finset α, (∀ i, s i ⊆ T ∧ digraph_directed_cycle_on D (s i)) ∧ Pairwise (fun i j => Disjoint (s i) (s j))) (C : Finset α) (hC : digraph_directed_cycle_on D C) (hcard : C.card = 3) (hnotdom : ∀ v ∉ C, (C.filter fun w => D.Adj v w).card ≤ 2) : ∃ s : Fin 4 → Finset α, (∀ i, digraph_directed_cycle_on D (s i)) ∧ Pairwise (fun i j => Disjoint (s i) (s j))
- Source
- Triangle-deletion step toward OP-110 using the outdegree-five three-cycle theorem.
- Verified
- 02 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- digraph_directed_cycle_ons is the vertex set of a directed cycle of D: its vertices can be listed without repetition, at least two of them, each with an arc to the…
The proof, explained
The proof removes the directed triangle C from the digraph to consider the induced subgraph on T = V \ C. Because no outside vertex dominates C (each has at most two out-neighbors in C), every vertex in T retains an out-degree of at least 7 - 2 = 5 into T, which also implies T is nonempty. Applying the three-cycle condition to T yields three pairwise vertex-disjoint directed cycles contained in T. Combining these three cycles with the original triangle C produces four pairwise vertex-disjoint directed cycles in the whole digraph.
The vertex set T = V \ C outside the triangle C is nonempty.
Define T as the complement of C in the vertex set V. If T were empty, then all vertices of the graph would belong to C, giving |V| ≤ |C| = 3. But since the graph is nonempty, taking any vertex a gives at least 7 out-neighbors, forcing |V| ≥ 7. Linear integer arithmetic (`omega`) derives False from 7 ≤ |V| ≤ 3.
uses
Finset.not_nonempty_iff_eq_empty.mp,Finset.card_le_card,Finset.filter_subsetlet T := Finset.univ \ C have hT : T.Nonempty := by by_contra hn have he : T = ∅ := Finset.not_nonempty_iff_eq_empty.mp hn have hs : (Finset.univ : Finset α) ⊆ C := by intro x hx by_cases hxc : x ∈ C · exact hxc have hxT : x ∈ T := by simp [T, hxc] rw [he] at hxT simp at hxT have hc := Finset.card_le_card hs obtain ⟨a⟩ := ‹Nonempty α› have hd := hdeg a have hdu := Finset.card_le_card (Finset.filter_subset (fun w => D.Adj a w) Finset.univ) omega
Every vertex in T has out-degree at least 5 into T.
For any vertex x ∈ T, we have x ∉ C, so by the non-domination hypothesis `hnotdom`, x has at most 2 out-neighbors in C. The total out-neighborhood of x (which has cardinality at least 7) is covered by the union of its out-neighbors in T and its out-neighbors in C. Therefore, the out-degree into T is at least 7 - 2 = 5, as verified by `omega`.
uses
Finset.mem_filter.mp,Finset.mem_union_right,Finset.mem_filter.mpr,Finset.mem_union_left,Finset.card_le_card,Finset.card_union_lehave hTdeg : ∀ x ∈ T, 5 ≤ (T.filter fun w => D.Adj x w).card := by intro x hx have hxc : x ∉ C := by simpa [T] using hx have h2 := hnotdom x hxc have hs : (Finset.univ.filter fun w => D.Adj x w) ⊆ (T.filter fun w => D.Adj x w) ∪ (C.filter fun w => D.Adj x w) := by intro w hw have hadj := (Finset.mem_filter.mp hw).2 by_cases hwc : w ∈ C · exact Finset.mem_union_right _ (Finset.mem_filter.mpr ⟨hwc, hadj⟩) · have hwT : w ∈ T := by simp [T, hwc] exact Finset.mem_union_left _ (Finset.mem_filter.mpr ⟨hwT, hadj⟩) have hc := Finset.card_le_card hs have hu := Finset.card_union_le (T.filter fun w => D.Adj x w) (C.filter fun w => D.Adj x w) have hd := hdeg x omega
There exist three pairwise vertex-disjoint directed cycles in T, each disjoint from C.
Applying the induction hypothesis `hthree` to the nonempty set T with minimum out-degree at least 5 yields a family t of three pairwise disjoint directed cycles contained in T. Since every cycle t(i) is a subset of T = V \ C, no cycle shares any vertex with C.
uses
Finset.disjoint_left.mprobtain ⟨t, ht, hpair⟩ := hthree T hT hTdeg have hdis : ∀ i, Disjoint C (t i) := by intro i apply Finset.disjoint_left.mpr intro x hx hxt have hxT := (ht i).1 hxt have hxc : x ∉ C := by simpa [T] using hxT exact hxc hx
The family f formed by adjoining C to the three cycles in T consists of four directed cycles in D.
We define f : Fin 4 → Finset α using `Fin.cases` so that f(0) = C and f(i + 1) = t(i). Exhausting the four possible values of i with `fin_cases` confirms that each f(i) is a directed cycle: f(0) = C is the given directed triangle, and each f(i + 1) = t(i) is one of the three cycles obtained from `hthree`.
uses
Fin.caseslet f : Fin 4 → Finset α := Fin.cases C t refine ⟨f, ?_, ?_⟩ · intro i fin_cases i · exact hC · exact (ht 0).2 · exact (ht 1).2 · exact (ht 2).2
The four directed cycles in f are pairwise vertex-disjoint.
For any distinct indices i ≠ j in Fin 4, we verify that f(i) and f(j) are disjoint by exhausting all 16 index pairs with `fin_cases`. The diagonal cases i = j are eliminated by the assumption i ≠ j. When one index is 0 and the other is nonzero, disjointness holds because C is disjoint from each t(k). When both indices are distinct nonzero elements, disjointness follows from the mutual disjointness of the three cycles in t.
· intro i j hij have h01 := hpair (show (0 : Fin 3) ≠ 1 by decide) have h02 := hpair (show (0 : Fin 3) ≠ 2 by decide) have h12 := hpair (show (1 : Fin 3) ≠ 2 by decide) fin_cases i <;> fin_cases j <;> first | exact (hij rfl).elim | exact hdis 0 | exact hdis 1 | exact hdis 2 | exact (hdis 0).symm | exact (hdis 1).symm | exact (hdis 2).symm | exact h01 | exact h02 | exact h12 | exact h01.symm | exact h02.symm | exact h12.symm
Finset.not_nonempty_iff_eq_empty.mp- A finite set is not nonempty only if it is the empty set.
Finset.card_le_card- If a finite set s is a subset of t, then |s| ≤ |t|.
Finset.filter_subset- The subset of elements of s satisfying a given predicate is a subset of s.
Finset.mem_filter.mp- If an element belongs to the filtered set {w ∈ s | p w}, then it belongs to s and satisfies p.
Finset.mem_filter.mpr- If an element belongs to s and satisfies p, then it belongs to the filtered set {w ∈ s | p w}.
Finset.mem_union_right- If an element belongs to t, then it belongs to s ∪ t.
Finset.mem_union_left- If an element belongs to s, then it belongs to s ∪ t.
Finset.card_union_le- The cardinality of the union of two finite sets is at most the sum of their cardinalities: |s ∪ t| ≤ |s| + |t|.
Finset.disjoint_left.mpr- If no element of s belongs to t, then s and t are disjoint.
Fin.cases- Defines a function on Fin (n + 1) by specifying its value at 0 and its values on the successors of elements in Fin n.
- The pairwise disjointness verification in the final step is carried out by exhaustive case analysis over all 16 index pairs in Fin 4 via `fin_cases`.
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.
theorem digraph_four_cycles_from_undominated_triangle (α : Type) [Fintype α] [DecidableEq α] [Nonempty α] (D : Digraph α) [DecidableRel D.Adj] (hdeg : ∀ v, 7 ≤ (Finset.univ.filter fun w => D.Adj v w).card) (hthree : ∀ T : Finset α, T.Nonempty → (∀ v ∈ T, 5 ≤ (T.filter fun w => D.Adj v w).card) → ∃ s : Fin 3 → Finset α, (∀ i, s i ⊆ T ∧ digraph_directed_cycle_on D (s i)) ∧ Pairwise (fun i j => Disjoint (s i) (s j))) (C : Finset α) (hC : digraph_directed_cycle_on D C) (hcard : C.card = 3) (hnotdom : ∀ v ∉ C, (C.filter fun w => D.Adj v w).card ≤ 2) : ∃ s : Fin 4 → Finset α, (∀ i, digraph_directed_cycle_on D (s i)) ∧ Pairwise (fun i j => Disjoint (s i) (s j)) := by let T := Finset.univ \ C have hT : T.Nonempty := by by_contra hn have he : T = ∅ := Finset.not_nonempty_iff_eq_empty.mp hn have hs : (Finset.univ : Finset α) ⊆ C := by intro x hx by_cases hxc : x ∈ C · exact hxc have hxT : x ∈ T := by simp [T, hxc] rw [he] at hxT simp at hxT have hc := Finset.card_le_card hs obtain ⟨a⟩ := ‹Nonempty α› have hd := hdeg a have hdu := Finset.card_le_card (Finset.filter_subset (fun w => D.Adj a w) Finset.univ) omega have hTdeg : ∀ x ∈ T, 5 ≤ (T.filter fun w => D.Adj x w).card := by intro x hx have hxc : x ∉ C := by simpa [T] using hx have h2 := hnotdom x hxc have hs : (Finset.univ.filter fun w => D.Adj x w) ⊆ (T.filter fun w => D.Adj x w) ∪ (C.filter fun w => D.Adj x w) := by intro w hw have hadj := (Finset.mem_filter.mp hw).2 by_cases hwc : w ∈ C · exact Finset.mem_union_right _ (Finset.mem_filter.mpr ⟨hwc, hadj⟩) · have hwT : w ∈ T := by simp [T, hwc] exact Finset.mem_union_left _ (Finset.mem_filter.mpr ⟨hwT, hadj⟩) have hc := Finset.card_le_card hs have hu := Finset.card_union_le (T.filter fun w => D.Adj x w) (C.filter fun w => D.Adj x w) have hd := hdeg x omega obtain ⟨t, ht, hpair⟩ := hthree T hT hTdeg have hdis : ∀ i, Disjoint C (t i) := by intro i apply Finset.disjoint_left.mpr intro x hx hxt have hxT := (ht i).1 hxt have hxc : x ∉ C := by simpa [T] using hxT exact hxc hx let f : Fin 4 → Finset α := Fin.cases C t refine ⟨f, ?_, ?_⟩ · intro i fin_cases i · exact hC · exact (ht 0).2 · exact (ht 1).2 · exact (ht 2).2 · intro i j hij have h01 := hpair (show (0 : Fin 3) ≠ 1 by decide) have h02 := hpair (show (0 : Fin 3) ≠ 2 by decide) have h12 := hpair (show (1 : Fin 3) ≠ 2 by decide) fin_cases i <;> fin_cases j <;> first | exact (hij rfl).elim | exact hdis 0 | exact hdis 1 | exact hdis 2 | exact (hdis 0).symm | exact (hdis 1).symm | exact (hdis 2).symm | exact h01 | exact h02 | exact h12 | exact h01.symm | exact h02.symm | exact h12.symm