digraph_four_cycles_from_two_cycles_few_bad
Two disjoint directed cycles with nonempty remainder can be extended to four under the displayed robust two-cycle condition if each outside vertex has at most five out-neighbors in their union and at most two have five.
Statement
theorem digraph_four_cycles_from_two_cycles_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₂) (hTne : (Finset.univ \ (C₁ ∪ C₂)).Nonempty) (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
- General cycle-pair deletion reduction for OP-110; the robust two-cycle hypothesis is a published 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…
- Used by 1
- digraph_two_cycles_boundary_obstructionIf a digraph of minimum outdegree seven has no four disjoint cycles, then for any two disjoint cycles with nonempty remainder either some…
The proof, explained
Given two disjoint directed cycles C₁ and C₂, the strategy is to apply the robust two-cycle hypothesis to the remaining vertex set T = V \ (C₁ ∪ C₂) to find two additional disjoint cycles. Because every vertex has out-degree at least 7 and at most 5 out-neighbors in C₁ ∪ C₂, each vertex in T has out-degree at least 7 - 5 = 2 restricted to T. Furthermore, any vertex in T with restricted out-degree exactly 2 must have at least 5 out-neighbors in C₁ ∪ C₂, which the hypotheses limit to at most two vertices. The robust hypothesis therefore produces two disjoint directed cycles inside T, which are disjoint from C₁ and C₂ by construction, yielding four pairwise disjoint directed cycles.
Let U = C₁ ∪ C₂ and T = V \ U; every vertex lies in T or U, and T is nonempty.
We define U as the union of the two given cycles and T as the remaining vertex set. By case analysis on whether a vertex belongs to U, every vertex lies in T or U. Nonemptiness of T is given directly by hypothesis hTne.
uses
Or.inr,Or.inllet U := C₁ ∪ C₂ let T := Finset.univ \ U 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 := hTne
For every vertex x, its out-neighbors in the graph are covered by its out-neighbors in T and its out-neighbors in U.
Any out-neighbor w of x lies in either T or U. Hence w is either an out-neighbor in T or an out-neighbor in U, so the full out-neighborhood is contained in the union of the two restricted out-neighborhoods.
uses
Finset.mem_filter.mp,Finset.mem_union_left,Finset.mem_filter.mpr,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.
For any vertex x in T, x is not in U. By hypothesis hnoall, x has at most 5 out-neighbors in U. Since the total out-degree of x is at least 7 by hdeg, and the out-neighbors are covered by T and U, the cardinality of the out-neighborhood in T must be at least 7 - 5 = 2 by linear arithmetic (omega).
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 out-degree exactly 2 in T.
If a vertex x in T has out-degree 2 in T, then because its total out-degree is at least 7, it must send at least 7 - 2 = 5 edges to U. Thus the set of degree-2 vertices in T is a subset of those with at least 5 out-neighbors in U. By hypothesis hfew, this set has at most 2 vertices, so by subset monotonicity of cardinality, at most 2 vertices in T have out-degree 2 in T.
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
The robust two-cycle hypothesis yields two disjoint directed cycles in T.
The set T is nonempty, every vertex in T has out-degree at least 2 within T, and at most two vertices have out-degree 2 in T. These are precisely the preconditions of hrobust, so applying it produces two directed cycles t₀, t₁ contained in T that are disjoint.
obtain ⟨t, ht, hpair⟩ := hrobust T hT hTdeg hbadThe two cycles in T are each disjoint from C₁ and from C₂.
Each cycle t(i) is a subset of T, which is disjoint from U = C₁ ∪ C₂. Thus no vertex of t(i) can lie in C₁ or C₂. Applying Finset.disjoint_left.mpr proves that C₁ is disjoint from t(i) and C₂ is disjoint from t(i).
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)
Assemble C₁, C₂, and the two new cycles into a 4-cycle family f and verify that each is a directed cycle.
We define f : Fin 4 → Finset α sending 0 to C₁, 1 to C₂, 2 to t₀, and 3 to t₁ using Fin.cases. Checking each index with fin_cases confirms that each component is a directed cycle, using hypotheses hC₁, hC₂ and the cycle property from the robust construction.
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 in f are pairwise disjoint.
For indices i ≠ j, exhaustive case analysis on (i, j) with fin_cases disposes of the diagonal i = j by contradiction and resolves all off-diagonal pairs using the disjointness of C₁ and C₂, the disjointness of C₁ and t(k), the disjointness of C₂ and t(k), or the mutual disjointness of t₀ and t₁, applying symmetry where appropriate.
· 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- Case analysis or recursion on Fin (n + 1), defined by a value at 0 and values at each successor
Finset.card_le_card- If a finite set s is a subset of t, then the cardinality of s is at most the cardinality of t
Finset.card_union_le- The cardinality of the union of two finite sets is at most the sum of their cardinalities
Finset.disjoint_left.mpr- Two finite sets are disjoint if no element of the first belongs to the second
Finset.mem_filter.mp- An element of a filtered set {x ∈ s | p x} belongs to s and satisfies p
Finset.mem_filter.mpr- An element that belongs to s and satisfies predicate p belongs to the filtered set {x ∈ s | p x}
Finset.mem_union_left- An element of s belongs to the union s ∪ t
Finset.mem_union_right- An element of t belongs to the union s ∪ t
Or.inl- Left introduction rule for disjunction: if a holds, then a ∨ b holds
Or.inr- Right introduction rule for disjunction: if b holds, then a ∨ b holds
- In steps 3 and 4, the linear arithmetic tactic omega closes the degree bounds by combining the minimum out-degree condition with the union bound on out-neighborhoods.
- In step 8, all 16 pairs of indices are checked exhaustively via fin_cases and discharged by the disjointness of the constituent cycles or contradiction on the diagonal.
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_two_cycles_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₂) (hTne : (Finset.univ \ (C₁ ∪ C₂)).Nonempty) (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 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 := hTne 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