digraph_four_cycles_two_triangles_few_bad
Suppose a finite loopless digraph has minimum outdegree at least seven and contains two disjoint directed triangles. If no outside vertex has six out-neighbors in their union, at most two outside vertices have five out-neighbors in their union, and the displayed robust two-cycle theorem holds on induced subsets, then the digraph contains four disjoint directed cycles.
Statement
theorem digraph_four_cycles_two_triangles_few_bad (α : Type) [Fintype α] [DecidableEq α] [Nonempty α] (D : Digraph α) [DecidableRel D.Adj] (hloop : ∀ v, ¬ D.Adj v v) (hdeg : ∀ v, 7 ≤ (Finset.univ.filter fun w => D.Adj v w).card) (hrobust : ∀ T : Finset α, T.Nonempty → (∀ v ∈ T, 2 ≤ (T.filter fun w => D.Adj v w).card) → (T.filter fun v => (T.filter fun w => D.Adj v w).card = 2).card ≤ 2 → ∃ s : Fin 2 → Finset α, (∀ i, s i ⊆ T ∧ digraph_directed_cycle_on D (s i)) ∧ Pairwise (fun i j => Disjoint (s i) (s j))) (C₁ C₂ : Finset α) (hC₁ : digraph_directed_cycle_on D C₁) (hC₂ : digraph_directed_cycle_on D C₂) (hdis : Disjoint C₁ C₂) (hcard₁ : C₁.card = 3) (hcard₂ : C₂.card = 3) (hnoall : ∀ v ∉ (C₁ ∪ C₂), ((C₁ ∪ C₂).filter fun w => D.Adj v w).card ≤ 5) (hfew : ((Finset.univ \ (C₁ ∪ C₂)).filter fun v => 5 ≤ ((C₁ ∪ C₂).filter fun w => D.Adj v w).card).card ≤ 2) : ∃ s : Fin 4 → Finset α, (∀ i, digraph_directed_cycle_on D (s i)) ∧ Pairwise (fun i j => Disjoint (s i) (s j))
- Source
- Two-triangle deletion mechanism for OP-110, using the degree-defect two-cycle theorem DOI:10.1137/080715792 Theorem 3.
- 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 finds four disjoint directed cycles by keeping the two given disjoint triangles C₁ and C₂ and finding two additional disjoint cycles in the complement T = V \ (C₁ ∪ C₂). Because |C₁ ∪ C₂| = 6 and the minimum outdegree is at least 7, T is nonempty, every vertex in T has outdegree at least 2 into T, and at most two vertices in T have outdegree exactly 2 into T. These conditions allow applying the assumed robust two-cycle theorem on T, yielding two disjoint cycles in T that are automatically disjoint from C₁ and C₂.
Let U = C₁ ∪ C₂ and T = V \ U; the set U has cardinality 6.
Define U as the union of the two disjoint triangles C₁ and C₂, and T as the remaining vertices. Because C₁ and C₂ each have 3 vertices and are disjoint, their union U has |U| = 3 + 3 = 6 vertices by Finset.card_union_of_disjoint.
uses
Finset.card_union_of_disjointlet U := C₁ ∪ C₂ let T := Finset.univ \ U have hU : U.card = 6 := by simp [U, Finset.card_union_of_disjoint hdis, hcard₁, hcard₂]
Every vertex in the digraph belongs to either T or U.
For any vertex x, either x ∈ U (the right disjunct) or x ∉ U, in which case x belongs to T = V \ U by definition (the left disjunct).
uses
Or.inl,Or.inrhave hcover : ∀ x : α, x ∈ T ∨ x ∈ U := by intro x by_cases hx : x ∈ U · exact Or.inr hx · exact Or.inl (by simp [T, hx])
The complementary vertex set T is nonempty.
Suppose for contradiction that T is empty. Then every vertex belongs to U, so the entire vertex set V satisfies |V| ≤ |U| = 6 by Finset.card_le_card. However, since the vertex type is nonempty, choosing any vertex a shows its outdegree is at least 7 by the minimum degree hypothesis (hdeg). Since its out-neighborhood is a subset of V by Finset.filter_subset, we obtain 7 ≤ |V| ≤ 6, a contradiction.
uses
Finset.not_nonempty_iff_eq_empty.mp,Finset.card_le_card,Finset.filter_subsethave hT : T.Nonempty := by by_contra hn have he : T = ∅ := Finset.not_nonempty_iff_eq_empty.mp hn have hs : (Finset.univ : Finset α) ⊆ U := by intro x hx rcases hcover x with h | h · rw [he] at h simp at h · exact h 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
For every vertex x, its out-neighbors partition into those in T and those in U.
Every out-neighbor w of x lies in either T or U by the coverage property. If w ∈ T, it is an out-neighbor in T; if w ∈ U, it is an out-neighbor in U. Thus the full out-neighborhood is a subset of the union of the out-neighborhoods in T and in U.
uses
Finset.mem_filter.mp,Finset.mem_filter.mpr,Finset.mem_union_left,Finset.mem_union_righthave hsplit : ∀ x : α, (Finset.univ.filter fun w => D.Adj x w) ⊆ (T.filter fun w => D.Adj x w) ∪ (U.filter fun w => D.Adj x w) := by intro x w hw have hadj := (Finset.mem_filter.mp hw).2 rcases hcover w with h | h · exact Finset.mem_union_left _ (Finset.mem_filter.mpr ⟨h, hadj⟩) · exact Finset.mem_union_right _ (Finset.mem_filter.mpr ⟨h, hadj⟩)
Every vertex in T has at least 2 out-neighbors in T.
Let x ∈ T. Because x ∉ U, the hypothesis hnoall guarantees that x has at most 5 out-neighbors in U. The total outdegree of x is at least 7 by hdeg, and it is at most the sum of its outdegrees into T and into U by Finset.card_union_le. Thus its outdegree into T is at least 7 - 5 = 2.
uses
Finset.card_le_card,Finset.card_union_lehave hTdeg : ∀ x ∈ T, 2 ≤ (T.filter fun w => D.Adj x w).card := by intro x hx have hxU : x ∉ U := by simpa [T] using hx have h5 : (U.filter fun w => D.Adj x w).card ≤ 5 := hnoall x hxU have hc := Finset.card_le_card (hsplit x) have hu := Finset.card_union_le (T.filter fun w => D.Adj x w) (U.filter fun w => D.Adj x w) have hd := hdeg x omega
At most two vertices in T have outdegree exactly 2 in T.
If a vertex x ∈ T has outdegree exactly 2 into T, then since its total outdegree is at least 7, it must have at least 7 - 2 = 5 out-neighbors in U. Therefore, the set of vertices in T with outdegree 2 into T is a subset of the vertices in T with at least 5 out-neighbors in U. By hypothesis hfew, there are at most 2 such vertices.
uses
Finset.mem_filter.mp,Finset.mem_filter.mpr,Finset.card_le_card,Finset.card_union_lehave hbad : (T.filter fun v => (T.filter fun w => D.Adj v w).card = 2).card ≤ 2 := by have hs : (T.filter fun v => (T.filter fun w => D.Adj v w).card = 2) ⊆ (T.filter fun v => 5 ≤ (U.filter fun w => D.Adj v w).card) := by intro x hx obtain ⟨hxT, hxdeg⟩ := Finset.mem_filter.mp hx apply Finset.mem_filter.mpr refine ⟨hxT, ?_⟩ have hc := Finset.card_le_card (hsplit x) have hu := Finset.card_union_le (T.filter fun w => D.Adj x w) (U.filter fun w => D.Adj x w) have hd := hdeg x omega have hh := Finset.card_le_card hs exact hh.trans hfew
There exist two disjoint directed cycles t₀, t₁ entirely contained in T.
Since T is nonempty, every vertex in T has outdegree at least 2 in T, and at most two vertices in T have outdegree 2 in T, the robust two-cycle hypothesis (hrobust) applies to the induced subgraph on T. This yields two disjoint directed cycles t₀, t₁ ⊆ T.
obtain ⟨t, ht, hpair⟩ := hrobust T hT hTdeg hbadBoth cycles t₀ and t₁ are disjoint from C₁ and C₂.
Each cycle tᵢ is contained in T. Since T = V \ (C₁ ∪ C₂), no vertex in tᵢ belongs to C₁ or C₂. By Finset.disjoint_left.mpr, this implies that tᵢ is disjoint from C₁ and from C₂.
uses
Finset.disjoint_left.mpr,Finset.mem_union_left,Finset.mem_union_righthave 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 hxU : x ∉ U := by simpa [T] using hxT exact hxU (Finset.mem_union_left _ hx) 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 hxU : x ∉ U := by simpa [T] using hxT exact hxU (Finset.mem_union_right _ hx)
The four sets C₁, C₂, t₀, t₁ form a family of four directed cycles.
Define the map f : Fin 4 → Finset α by 0 ↦ C₁, 1 ↦ C₂, 2 ↦ t₀, and 3 ↦ t₁ via Fin.cases. Exhaustive check on the four indices confirms each f i is a directed cycle: C₁ and C₂ by the theorem hypotheses (hC₁, hC₂), and t₀ and t₁ from the robust hypothesis output.
uses
Fin.caseslet f : Fin 4 → Finset α := Fin.cases C₁ (Fin.cases C₂ t) refine ⟨f, ?_, ?_⟩ · intro i fin_cases i · exact hC₁ · exact hC₂ · exact (ht 0).2 · exact (ht 1).2
The four directed cycles are pairwise disjoint.
For any distinct indices i ≠ j in {0, 1, 2, 3}, disjointness is verified by cases. Disjointness between C₁ and C₂ comes from hdis; disjointness between C₁ or C₂ and either t₀ or t₁ comes from hdis₁ and hdis₂; and disjointness between t₀ and t₁ comes from the pairwise disjointness of t (hpair).
· intro i j hij have ht01 := hpair (show (0 : Fin 2) ≠ 1 by decide) fin_cases i <;> fin_cases j <;> first | exact (hij rfl).elim | exact hdis | exact hdis.symm | exact hdis₁ 0 | exact hdis₁ 1 | exact (hdis₁ 0).symm | exact (hdis₁ 1).symm | exact hdis₂ 0 | exact hdis₂ 1 | exact (hdis₂ 0).symm | exact (hdis₂ 1).symm | exact ht01 | exact ht01.symm
Fin.cases- Defines a function on Fin (n + 1) by giving its value at 0 and its values on the successors of Fin n.
Finset.card_le_card- If a finite set S is a subset of T, then |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.card_union_of_disjoint- The cardinality of the union of two disjoint finite sets is the sum of their cardinalities: |S ∪ T| = |S| + |T|.
Finset.disjoint_left.mpr- Two finite sets are disjoint if no element of the first belongs to the second.
Finset.filter_subset- Filtering a finite set by a predicate produces a subset of the original set.
Finset.mem_filter.mp- If an element belongs to a filtered set, then it belongs to the base set and satisfies the predicate.
Finset.mem_filter.mpr- If an element belongs to a set and satisfies a predicate, then it belongs to the filtered set.
Finset.mem_union_left- An element in S also belongs to S ∪ T.
Finset.mem_union_right- An element in T also belongs to S ∪ T.
Finset.not_nonempty_iff_eq_empty.mp- A finite set that is not nonempty is empty.
Or.inl- From a proof of A, establishes the disjunction A ∨ B.
Or.inr- From a proof of B, establishes the disjunction A ∨ B.
- Step 10 verifies the pairwise disjointness of the four cycles by finite case exhaustion (via `fin_cases`) over all 16 index pairs (i, j) in {0, 1, 2, 3}².
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_two_triangles_few_bad (α : Type) [Fintype α] [DecidableEq α] [Nonempty α] (D : Digraph α) [DecidableRel D.Adj] (hloop : ∀ v, ¬ D.Adj v v) (hdeg : ∀ v, 7 ≤ (Finset.univ.filter fun w => D.Adj v w).card) (hrobust : ∀ T : Finset α, T.Nonempty → (∀ v ∈ T, 2 ≤ (T.filter fun w => D.Adj v w).card) → (T.filter fun v => (T.filter fun w => D.Adj v w).card = 2).card ≤ 2 → ∃ s : Fin 2 → Finset α, (∀ i, s i ⊆ T ∧ digraph_directed_cycle_on D (s i)) ∧ Pairwise (fun i j => Disjoint (s i) (s j))) (C₁ C₂ : Finset α) (hC₁ : digraph_directed_cycle_on D C₁) (hC₂ : digraph_directed_cycle_on D C₂) (hdis : Disjoint C₁ C₂) (hcard₁ : C₁.card = 3) (hcard₂ : C₂.card = 3) (hnoall : ∀ v ∉ (C₁ ∪ C₂), ((C₁ ∪ C₂).filter fun w => D.Adj v w).card ≤ 5) (hfew : ((Finset.univ \ (C₁ ∪ C₂)).filter fun v => 5 ≤ ((C₁ ∪ C₂).filter fun w => D.Adj v w).card).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 U := C₁ ∪ C₂ let T := Finset.univ \ U have hU : U.card = 6 := by simp [U, Finset.card_union_of_disjoint hdis, hcard₁, hcard₂] have hcover : ∀ x : α, x ∈ T ∨ x ∈ U := by intro x by_cases hx : x ∈ U · exact Or.inr hx · exact Or.inl (by simp [T, hx]) have hT : T.Nonempty := by by_contra hn have he : T = ∅ := Finset.not_nonempty_iff_eq_empty.mp hn have hs : (Finset.univ : Finset α) ⊆ U := by intro x hx rcases hcover x with h | h · rw [he] at h simp at h · exact h 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 hsplit : ∀ x : α, (Finset.univ.filter fun w => D.Adj x w) ⊆ (T.filter fun w => D.Adj x w) ∪ (U.filter fun w => D.Adj x w) := by intro x w hw have hadj := (Finset.mem_filter.mp hw).2 rcases hcover w with h | h · exact Finset.mem_union_left _ (Finset.mem_filter.mpr ⟨h, hadj⟩) · exact Finset.mem_union_right _ (Finset.mem_filter.mpr ⟨h, hadj⟩) have hTdeg : ∀ x ∈ T, 2 ≤ (T.filter fun w => D.Adj x w).card := by intro x hx have hxU : x ∉ U := by simpa [T] using hx have h5 : (U.filter fun w => D.Adj x w).card ≤ 5 := hnoall x hxU have hc := Finset.card_le_card (hsplit x) have hu := Finset.card_union_le (T.filter fun w => D.Adj x w) (U.filter fun w => D.Adj x w) have hd := hdeg x omega have hbad : (T.filter fun v => (T.filter fun w => D.Adj v w).card = 2).card ≤ 2 := by have hs : (T.filter fun v => (T.filter fun w => D.Adj v w).card = 2) ⊆ (T.filter fun v => 5 ≤ (U.filter fun w => D.Adj v w).card) := by intro x hx obtain ⟨hxT, hxdeg⟩ := Finset.mem_filter.mp hx apply Finset.mem_filter.mpr refine ⟨hxT, ?_⟩ have hc := Finset.card_le_card (hsplit x) have hu := Finset.card_union_le (T.filter fun w => D.Adj x w) (U.filter fun w => D.Adj x w) have hd := hdeg x omega have hh := Finset.card_le_card hs exact hh.trans hfew obtain ⟨t, ht, hpair⟩ := hrobust T hT hTdeg hbad 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 hxU : x ∉ U := by simpa [T] using hxT exact hxU (Finset.mem_union_left _ hx) 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 hxU : x ∉ U := by simpa [T] using hxT exact hxU (Finset.mem_union_right _ hx) let f : Fin 4 → Finset α := Fin.cases C₁ (Fin.cases C₂ t) refine ⟨f, ?_, ?_⟩ · intro i fin_cases i · exact hC₁ · exact hC₂ · exact (ht 0).2 · exact (ht 1).2 · intro i j hij have ht01 := hpair (show (0 : Fin 2) ≠ 1 by decide) fin_cases i <;> fin_cases j <;> first | exact (hij rfl).elim | exact hdis | exact hdis.symm | exact hdis₁ 0 | exact hdis₁ 1 | exact (hdis₁ 0).symm | exact (hdis₁ 1).symm | exact hdis₂ 0 | exact hdis₂ 1 | exact (hdis₂ 0).symm | exact (hdis₂ 1).symm | exact ht01 | exact ht01.symm