digraph_two_cycles_boundary_obstruction
If a digraph of minimum outdegree seven has no four disjoint cycles, then for any two disjoint cycles with nonempty remainder either some outside vertex has at least six out-neighbors in their union or at least three outside vertices have at least five, assuming the displayed robust two-cycle condition.
Statement
theorem digraph_two_cycles_boundary_obstruction (α : 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) (hno : ¬ ∃ s : Fin 4 → Finset α, (∀ i, digraph_directed_cycle_on D (s i)) ∧ Pairwise (fun i j => Disjoint (s i) (s j))) : (∃ v ∉ (C₁ ∪ C₂), 6 ≤ ((C₁ ∪ C₂).filter fun w => D.Adj v w).card) ∨ 3 ≤ ((Finset.univ \ (C₁ ∪ C₂)).filter fun v => 5 ≤ ((C₁ ∪ C₂).filter fun w => D.Adj v w).card).card
- 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 2
- 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…
- digraph_four_cycles_from_two_cycles_few_badTwo disjoint directed cycles with nonempty remainder can be extended to four under the displayed robust two-cycle condition if each…
The proof, explained
The proof proceeds by contradiction. Assuming that neither boundary obstruction condition holds, every vertex outside C₁ ∪ C₂ has at most five out-neighbors in C₁ ∪ C₂, and at most two outside vertices have at least five out-neighbors in C₁ ∪ C₂. These two bounds fulfill the preconditions of `digraph_four_cycles_from_two_cycles_few_bad`, which produces four pairwise disjoint directed cycles and contradicts the assumption that no four such cycles exist.
Assume, for contradiction, that neither boundary condition holds.
We use classical logic and assume the negation of the disjunction: there is no outside vertex with at least 6 out-neighbors in C₁ ∪ C₂, and the number of outside vertices with at least 5 out-neighbors in C₁ ∪ C₂ is strictly less than 3.
classical by_contra hEvery outside vertex has at most 5 out-neighbors in C₁ ∪ C₂.
For any vertex v ∉ C₁ ∪ C₂, if its out-degree into C₁ ∪ C₂ were not at most 5, it would have at least 6 out-neighbors in C₁ ∪ C₂ by basic integer arithmetic. This would witness the first branch of the conclusion disjunction, contradicting our assumption h.
have hnoall : ∀ v ∉ (C₁ ∪ C₂), ((C₁ ∪ C₂).filter fun w => D.Adj v w).card ≤ 5 := by intro v hv by_contra hh apply h left exact ⟨v, hv, by omega⟩
At most 2 outside vertices have at least 5 out-neighbors in C₁ ∪ C₂.
If the number of vertices in the complement with at least 5 out-neighbors in C₁ ∪ C₂ were not at most 2, it would be at least 3 by basic integer arithmetic. This would satisfy the second branch of the conclusion disjunction, contradicting our assumption h.
have hfew : ((Finset.univ \ (C₁ ∪ C₂)).filter fun v => 5 ≤ ((C₁ ∪ C₂).filter fun w => D.Adj v w).card).card ≤ 2 := by by_contra hh apply h right omega
The assumption leads to a contradiction, concluding the proof.
With the upper bound of 5 out-neighbors for all outside vertices and at most 2 vertices reaching 5, lemma `digraph_four_cycles_from_two_cycles_few_bad` guarantees that the digraph contains 4 pairwise disjoint directed cycles. This directly contradicts the hypothesis hno that no 4 pairwise disjoint directed cycles exist.
uses
digraph_four_cycles_from_two_cycles_few_badexact hno (digraph_four_cycles_from_two_cycles_few_bad α D hloop hdeg hrobust C₁ C₂ hC₁ hC₂ hdis hTne hnoall hfew)
digraph_four_cycles_from_two_cycles_few_bad- Under the given hypotheses (minimum outdegree at least 7, no loops, robust two-cycle condition), if there are two disjoint directed cycles whose complement is nonempty, every vertex outside has at most 5 out-neighbors in their union, and at most 2 outside vertices have at least 5 out-neighbors in their union, then the digraph contains 4 pairwise disjoint directed cycles.
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_two_cycles_boundary_obstruction (α : 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) (hno : ¬ ∃ s : Fin 4 → Finset α, (∀ i, digraph_directed_cycle_on D (s i)) ∧ Pairwise (fun i j => Disjoint (s i) (s j))) : (∃ v ∉ (C₁ ∪ C₂), 6 ≤ ((C₁ ∪ C₂).filter fun w => D.Adj v w).card) ∨ 3 ≤ ((Finset.univ \ (C₁ ∪ C₂)).filter fun v => 5 ≤ ((C₁ ∪ C₂).filter fun w => D.Adj v w).card).card := by classical by_contra h have hnoall : ∀ v ∉ (C₁ ∪ C₂), ((C₁ ∪ C₂).filter fun w => D.Adj v w).card ≤ 5 := by intro v hv by_contra hh apply h left exact ⟨v, hv, by omega⟩ have hfew : ((Finset.univ \ (C₁ ∪ C₂)).filter fun v => 5 ≤ ((C₁ ∪ C₂).filter fun w => D.Adj v w).card).card ≤ 2 := by by_contra hh apply h right omega exact hno (digraph_four_cycles_from_two_cycles_few_bad α D hloop hdeg hrobust C₁ C₂ hC₁ hC₂ hdis hTne hnoall hfew)