digraph_four_cycles_from_small_cut
In a loopless digraph of minimum outdegree seven, if B is nonempty and all arcs leaving B end in a set S of at most two vertices, a directed cycle in the in-neighborhood of a vertex outside B and S combines with three directed cycles in B to give four disjoint cycles, provided the displayed outdegree-five theorem holds.
Statement
theorem digraph_four_cycles_from_small_cut (α : 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) (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))) (B S : Finset α) (hB : B.Nonempty) (hS : S.card ≤ 2) (hcut : ∀ b ∈ B, ∀ w, D.Adj b w → w ∈ B ∨ w ∈ S) (a : α) (haB : a ∉ B) (haS : a ∉ S) (C : Finset α) (hC : digraph_directed_cycle_on D C) (hin : ∀ v ∈ C, D.Adj v a) : ∃ s : Fin 4 → Finset α, (∀ i, digraph_directed_cycle_on D (s i)) ∧ Pairwise (fun i j => Disjoint (s i) (s j))
- Source
- Adaptation of the strong-connectivity argument in arXiv:1805.02999, Section 3, to the four-cycle minimum-counterexample route for OP-110.
- 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 constructs four pairwise disjoint directed cycles by combining the given cycle C with three disjoint cycles inside B. First, because every arc leaving B ends in B or S and |S| ≤ 2, each vertex in B retains at least 7 - 2 = 5 out-neighbors in B, satisfying the outdegree-5 theorem hypothesis to obtain three disjoint directed cycles in B. Finally, the cycle C must be disjoint from all three cycles in B because any vertex in C has an arc to a, which cannot originate in B since a is outside both B and S.
Every vertex in B has at least 5 out-neighbors in B.
For any vertex b ∈ B, the cut condition (hcut) implies that every out-neighbor of b lies in B ∪ S. Hence, the out-neighborhood of b in the entire digraph is a subset of its out-neighborhood in B united with S. Since the outdegree of b in the digraph is at least 7 (hdeg) and |S| ≤ 2 (hS), subadditivity of cardinality (Finset.card_union_le) and subset monotonicity (Finset.card_le_card) imply that b has at least 7 - 2 = 5 out-neighbors in B. Linear integer arithmetic (omega) finishes the calculation.
uses
Finset.mem_filter.mp,Finset.mem_union_left,Finset.mem_filter.mpr,Finset.mem_union_right,Finset.card_le_card,Finset.card_union_lehave hBdeg : ∀ b ∈ B, 5 ≤ (B.filter fun w => D.Adj b w).card := by intro b hb have hs : (Finset.univ.filter fun w => D.Adj b w) ⊆ (B.filter fun w => D.Adj b w) ∪ S := by intro w hw have hadj := (Finset.mem_filter.mp hw).2 rcases hcut b hb w hadj with hwB | hwS · exact Finset.mem_union_left _ (Finset.mem_filter.mpr ⟨hwB, hadj⟩) · exact Finset.mem_union_right _ hwS have hc := Finset.card_le_card hs have hu := Finset.card_union_le (B.filter fun w => D.Adj b w) S have hd := hdeg b omega
There exist three pairwise disjoint directed cycles contained entirely in B.
Since B is nonempty and each vertex in B has outdegree at least 5 within B, the hypothesis hthree applies to B, yielding a family t of three directed cycles in B that are pairwise disjoint.
obtain ⟨t, ht, hpair⟩ := hthree B hB hBdegThe cycle C is disjoint from each of the three cycles in B.
To show C is disjoint from t(i) (via Finset.disjoint_left.mpr), suppose for contradiction that some vertex x lies in both C and t(i). Because t(i) ⊆ B, x must belong to B. The assumption hin gives an arc from x to a. But the cut condition hcut forces any arc out of B to land in B or S, meaning a ∈ B or a ∈ S. This directly contradicts the hypotheses that a ∉ B and a ∉ S.
uses
Finset.disjoint_left.mprhave hdis : ∀ i, Disjoint C (t i) := by intro i apply Finset.disjoint_left.mpr intro x hx hxt have hxB := (ht i).1 hxt rcases hcut x hxB a (hin x hx) with h | h · exact haB h · exact haS h
Combining C with the three cycles in B gives a 4-element family of directed cycles.
We define f : Fin 4 → Finset α using Fin.cases by placing C at index 0 and t at indices 1, 2, 3. Case analysis on i : Fin 4 shows that f(0) is a directed cycle by hC, and f(1), f(2), f(3) are directed cycles by the properties of t.
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 cycles in f are pairwise disjoint.
For distinct indices i ≠ j in Fin 4, we establish Disjoint (f i) (f j). The pairwise disjointness of t(0), t(1), t(2) is extracted from hpair. An exhaustive case split on all pairs (i, j) then shows disjointness: the diagonal i = j is ruled out by i ≠ j; cases with one index equal to 0 follow from the disjointness of C from each t(k); and cases with both indices in {1, 2, 3} follow from the pairwise disjointness of the 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
Fin.cases- Defines a dependent function on Fin (n + 1) by its value at 0 and its values on the remaining n elements.
Finset.card_le_card- If one finite set is a subset of another, its cardinality is less than or equal to that of the other.
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 set belongs to the second set.
Finset.mem_filter.mp- If an element belongs to a filtered finite set, then it belongs to the base set and satisfies the predicate.
Finset.mem_filter.mpr- If an element belongs to a finite set and satisfies a predicate, then it belongs to the filtered finite set.
Finset.mem_union_left- An element in a finite set s also belongs to the union s ∪ t.
Finset.mem_union_right- An element in a finite set t also belongs to the union s ∪ t.
- In the final step (lines 46–64), Lean exhaustively checks all 16 index pairs (i, j) in Fin 4 using the `fin_cases` tactic and the `first` combinator to establish pairwise disjointness mechanically.
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_small_cut (α : 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) (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))) (B S : Finset α) (hB : B.Nonempty) (hS : S.card ≤ 2) (hcut : ∀ b ∈ B, ∀ w, D.Adj b w → w ∈ B ∨ w ∈ S) (a : α) (haB : a ∉ B) (haS : a ∉ S) (C : Finset α) (hC : digraph_directed_cycle_on D C) (hin : ∀ v ∈ C, D.Adj v a) : ∃ s : Fin 4 → Finset α, (∀ i, digraph_directed_cycle_on D (s i)) ∧ Pairwise (fun i j => Disjoint (s i) (s j)) := by have hBdeg : ∀ b ∈ B, 5 ≤ (B.filter fun w => D.Adj b w).card := by intro b hb have hs : (Finset.univ.filter fun w => D.Adj b w) ⊆ (B.filter fun w => D.Adj b w) ∪ S := by intro w hw have hadj := (Finset.mem_filter.mp hw).2 rcases hcut b hb w hadj with hwB | hwS · exact Finset.mem_union_left _ (Finset.mem_filter.mpr ⟨hwB, hadj⟩) · exact Finset.mem_union_right _ hwS have hc := Finset.card_le_card hs have hu := Finset.card_union_le (B.filter fun w => D.Adj b w) S have hd := hdeg b omega obtain ⟨t, ht, hpair⟩ := hthree B hB hBdeg have hdis : ∀ i, Disjoint C (t i) := by intro i apply Finset.disjoint_left.mpr intro x hx hxt have hxB := (ht i).1 hxt rcases hcut x hxB a (hin x hx) with h | h · exact haB h · exact haS h 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