digraph_four_cycles_from_digon_and_three_cycle_theorem
If a finite loopless digraph has minimum outdegree seven, contains a directed two-cycle, and every nonempty vertex subset whose induced minimum outdegree is five contains three disjoint directed cycles, then it contains four disjoint directed cycles.
Statement
theorem digraph_four_cycles_from_digon_and_three_cycle_theorem (α : 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))) (u v : α) (huv : D.Adj u v) (hvu : D.Adj v u) : ∃ s : Fin 4 → Finset α, (∀ i, digraph_directed_cycle_on D (s i)) ∧ Pairwise (fun i j => Disjoint (s i) (s j))
- Source
- Digon reduction in the minimum-counterexample route for OP-110, using the published outdegree-five theorem for three cycles.
- 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
Since the digraph is loopless, the directed 2-cycle between u and v is on two distinct vertices, forming a directed cycle {u, v}. Deleting {u, v} leaves the nonempty vertex subset T = V \ {u, v}, on which every vertex retains an outdegree of at least 7 - 2 = 5. By the three-cycle hypothesis applied to T, there are three pairwise disjoint directed cycles contained in T. Adjoining the disjoint 2-cycle {u, v} yields four pairwise disjoint directed cycles in the digraph.
The vertices u and v are distinct, and T is defined as the set of vertices outside {u, v}.
Because the digraph has no self-loops (hloop), the existence of a directed edge from u to v implies u ≠ v. We define T = V \ {u, v} by removing u and v from the universal vertex set.
have huvne : u ≠ v := by intro h; subst v; exact hloop u huv let T : Finset α := (Finset.univ.erase u).erase v
The vertex set of the digraph has cardinality at least 7.
The hypothesis hdeg states that every vertex has outdegree at least 7. In particular, the out-neighborhood of u has size at least 7, and since it is a subset of the universal vertex set (Finset.filter_subset), the total number of vertices |V| is at least 7 by monotonicity of cardinality (Finset.card_le_card).
uses
Finset.card_le_card,Finset.filter_subsethave hcard : 7 ≤ (Finset.univ : Finset α).card := (hdeg u).trans (Finset.card_le_card (Finset.filter_subset _ _))The vertex set T is nonempty.
Suppose for contradiction that T were empty (Finset.not_nonempty_iff_eq_empty.mp). Then every vertex in V must equal u or v, so V ⊆ {u, v}. By monotonicity of cardinality (Finset.card_le_card), this would mean |V| ≤ |{u, v}| ≤ 2. But |V| ≥ 7, which gives a contradiction via linear arithmetic (omega).
uses
Finset.not_nonempty_iff_eq_empty.mp,Finset.card_le_cardhave hT : T.Nonempty := by by_contra hn have he : T = ∅ := Finset.not_nonempty_iff_eq_empty.mp hn have hs : (Finset.univ : Finset α) ⊆ {u,v} := by intro x hx by_cases hxu : x = u · simp [hxu] by_cases hxv : x = v · simp [hxv] have : x ∈ T := by simp [T, hxu, hxv] rw [he] at this simp at this have hh := Finset.card_le_card hs have hp : ({u,v} : Finset α).card ≤ 2 := by simp [huvne] omega
Every vertex in T has at least 5 out-neighbors in T.
Let x ∈ T. Any out-neighbor w of x in the entire digraph (Finset.mem_filter.mp) is either in {u, v} or in T, so the full out-neighborhood of x is a subset of the union of its out-neighborhood in T and {u, v} (Finset.mem_union_left, Finset.mem_filter.mpr). By subadditivity of cardinality (Finset.card_le_card, Finset.card_union_le), the total outdegree is at most the induced outdegree in T plus |{u, v}| ≤ 2. Since the total outdegree is at least 7 (hdeg), linear arithmetic (omega) implies the induced outdegree in T is at least 5.
uses
Finset.mem_filter.mp,Finset.mem_union_left,Finset.mem_filter.mpr,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 hs : (Finset.univ.filter fun w => D.Adj x w) ⊆ (T.filter fun w => D.Adj x w) ∪ {u,v} := by intro w hw have hadj := (Finset.mem_filter.mp hw).2 by_cases hwu : w = u · simp [hwu] by_cases hwv : w = v · simp [hwv] have hwT : w ∈ T := by simp [T, hwu, hwv] exact Finset.mem_union_left _ (Finset.mem_filter.mpr ⟨hwT, hadj⟩) have hh := Finset.card_le_card hs have hu := Finset.card_union_le (T.filter fun w => D.Adj x w) ({u,v} : Finset α) have hp : ({u,v} : Finset α).card ≤ 2 := by simp [huvne] have hd := hdeg x omega
There exist three pairwise disjoint directed cycles contained in T.
Applying the hypothesis hthree to the nonempty set T and its induced minimum outdegree bound of 5 yields a family t of three directed cycles in D, each contained in T, which are pairwise disjoint.
obtain ⟨t, ht, hpair⟩ := hthree T hT hTdegThe two-element set {u, v} forms a directed cycle in D.
We provide the list [u, v] as the cycle. Since u ≠ v and the directed edges u → v and v → u exist, [u, v] is a valid directed 2-cycle on the set {u, v}.
have h2 : digraph_directed_cycle_on D ({u,v} : Finset α) := by refine ⟨[u,v], ?_⟩ simp [huvne, huv, hvu]
The 2-cycle {u, v} is disjoint from each of the three cycles in T.
To show disjointness (Finset.disjoint_left.mpr), suppose an element x belongs to both {u, v} and t(i). Since t(i) ⊆ T, x ∈ T, which means x ≠ u and x ≠ v (Finset.mem_erase, Finset.mem_univ, and_true). However, x ∈ {u, v} implies x = u or x = v (Finset.mem_insert, Finset.mem_singleton), yielding a contradiction.
uses
Finset.disjoint_left.mpr,Finset.mem_erase,Finset.mem_univ,and_true,Finset.mem_insert,Finset.mem_singletonhave hdis : ∀ i, Disjoint ({u,v} : Finset α) (t i) := by intro i apply Finset.disjoint_left.mpr intro x hx hxt have hxT := (ht i).1 hxt simp only [T, Finset.mem_erase, Finset.mem_univ, and_true] at hxT simp only [Finset.mem_insert, Finset.mem_singleton] at hx rcases hx with rfl | rfl <;> simp_all
Construct a family f of four sets by prepending {u, v} to the three cycles from T, and verify each is a directed cycle.
Using Fin.cases, define f : Fin 4 → Finset α by setting f(0) = {u, v} and f(i+1) = t(i). By casing on i ∈ {0, 1, 2, 3}, f(0) is the 2-cycle {u, v} and f(1), f(2), f(3) are the three directed cycles t(0), t(1), t(2).
uses
Fin.caseslet f : Fin 4 → Finset α := Fin.cases {u,v} t refine ⟨f, ?_, ?_⟩ · intro i fin_cases i · exact h2 · exact (ht 0).2 · exact (ht 1).2 · exact (ht 2).2
The four directed cycles in f are pairwise disjoint.
For distinct indices i ≠ j in Fin 4, we examine all pairs. When i = j, the hypothesis i ≠ j gives an immediate contradiction. When one index is 0 and the other is nonzero, disjointness follows from {u, v} being disjoint from each t(k). When both indices are nonzero, disjointness follows from the pairwise disjointness of t(0), t(1), and t(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
and_true- For any proposition p, p ∧ True is equivalent to p.
Fin.cases- Defines a function on Fin (n + 1) by specifying its value at 0 and its values on successors i.succ.
Finset.card_le_card- If s ⊆ 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.disjoint_left.mpr- If no element of s belongs to t, then s and t are disjoint.
Finset.mem_erase- An element a belongs to s \ {b} if and only if a ≠ b and a ∈ 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_insert- An element belongs to {b} ∪ s if and only if it equals b or belongs to s.
Finset.mem_singleton- An element belongs to the singleton {a} if and only if it equals a.
Finset.mem_univ- Every element of a finite type belongs to the universal set Finset.univ.
Finset.mem_union_left- If a ∈ s, then a ∈ s ∪ t.
Finset.not_nonempty_iff_eq_empty.mp- If a finite set is not nonempty, then it is the empty set.
Finset.filter_subset- The subset of elements of s satisfying a predicate p is a subset of s.
- The pairwise disjointness of the four cycles (lines 68–86) is verified in Lean by an exhaustive case analysis across all 16 pairs of indices in Fin 4, rather than using symmetry.
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_digon_and_three_cycle_theorem (α : 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))) (u v : α) (huv : D.Adj u v) (hvu : D.Adj v u) : ∃ s : Fin 4 → Finset α, (∀ i, digraph_directed_cycle_on D (s i)) ∧ Pairwise (fun i j => Disjoint (s i) (s j)) := by have huvne : u ≠ v := by intro h; subst v; exact hloop u huv let T : Finset α := (Finset.univ.erase u).erase v have hcard : 7 ≤ (Finset.univ : Finset α).card := (hdeg u).trans (Finset.card_le_card (Finset.filter_subset _ _)) 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,v} := by intro x hx by_cases hxu : x = u · simp [hxu] by_cases hxv : x = v · simp [hxv] have : x ∈ T := by simp [T, hxu, hxv] rw [he] at this simp at this have hh := Finset.card_le_card hs have hp : ({u,v} : Finset α).card ≤ 2 := by simp [huvne] omega have hTdeg : ∀ x ∈ T, 5 ≤ (T.filter fun w => D.Adj x w).card := by intro x hx have hs : (Finset.univ.filter fun w => D.Adj x w) ⊆ (T.filter fun w => D.Adj x w) ∪ {u,v} := by intro w hw have hadj := (Finset.mem_filter.mp hw).2 by_cases hwu : w = u · simp [hwu] by_cases hwv : w = v · simp [hwv] have hwT : w ∈ T := by simp [T, hwu, hwv] exact Finset.mem_union_left _ (Finset.mem_filter.mpr ⟨hwT, hadj⟩) have hh := Finset.card_le_card hs have hu := Finset.card_union_le (T.filter fun w => D.Adj x w) ({u,v} : Finset α) have hp : ({u,v} : Finset α).card ≤ 2 := by simp [huvne] have hd := hdeg x omega obtain ⟨t, ht, hpair⟩ := hthree T hT hTdeg have h2 : digraph_directed_cycle_on D ({u,v} : Finset α) := by refine ⟨[u,v], ?_⟩ simp [huvne, huv, hvu] have hdis : ∀ i, Disjoint ({u,v} : Finset α) (t i) := by intro i apply Finset.disjoint_left.mpr intro x hx hxt have hxT := (ht i).1 hxt simp only [T, Finset.mem_erase, Finset.mem_univ, and_true] at hxT simp only [Finset.mem_insert, Finset.mem_singleton] at hx rcases hx with rfl | rfl <;> simp_all let f : Fin 4 → Finset α := Fin.cases {u,v} t refine ⟨f, ?_, ?_⟩ · intro i fin_cases i · exact h2 · 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