digraph_small_overlap_cycle_packing_step
The k-cycle theorem at outdegree d implies the (k+1)-cycle theorem for loopless arc-dominated digraphs of minimum outdegree at least d+2 when repeated common-predecessor incidences are fewer than one third of the order.
Statement
theorem digraph_small_overlap_cycle_packing_step (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (k d : ℕ) (hloop : ∀ v, ¬ D.Adj v v) (hdeg : ∀ v, d + 2 ≤ (Finset.univ.filter fun w => D.Adj v w).card) (hdom : ∀ u v, D.Adj u v → ∃ w, D.Adj w u ∧ D.Adj w v) (hsmall : 3 * ((∑ v : α, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) - (digraph_common_predecessor_graph D).edgeFinset.card) < Fintype.card α) (hpack : ∀ T : Finset α, T.Nonempty → (∀ v ∈ T, d ≤ (T.filter fun w => D.Adj v w).card) → ∃ s : Fin k → Finset α, (∀ i, s i ⊆ T ∧ digraph_directed_cycle_on D (s i)) ∧ Pairwise (fun i j => Disjoint (s i) (s j))) : ∃ s : Fin (k + 1) → Finset α, (∀ i, digraph_directed_cycle_on D (s i)) ∧ Pairwise (fun i j => Disjoint (s i) (s j))
- Source
- General small-overlap cycle-packing induction for OP-110.
- Verified
- 03 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- digraph_small_overlap_arc_dominated_cycle_packing_stepThe k-cycle theorem at outdegree d implies the (k+1)-cycle theorem for oriented arc-dominated digraphs of minimum outdegree at least d+2…
- digraph_digon_cycle_packing_stepA directed two-cycle can be added to any k-cycle packing theorem two outdegree units lower.
- digraph_common_predecessor_graphThe simple graph joining distinct vertices that have a common in-neighbor in the digraph.
- 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 3
- digraph_127_four_cycles_under_extremal_and_cycle_criteriaA 7-outregular oriented digraph on 127 vertices with dominated arcs and a cycle in every in-neighborhood contains four disjoint directed…
- digraph_126_four_cycles_under_extremal_and_cycle_criteriaA loopless oriented seven-outregular digraph on 126 vertices whose arcs have common predecessors and whose every in-neighborhood contains…
- digraph_125_no_four_cycles_overlap_windowFor a loopless oriented seven-outregular digraph on 125 vertices with dominated arcs, a cycle in each in-neighborhood, and no four…
The proof, explained
The proof proceeds by case analysis on whether the digraph contains a 2-cycle (a digon). If a 2-cycle exists, removing its two vertices leaves a sub-digraph of minimum outdegree at least d, which contains k disjoint cycles by the induction hypothesis, giving k+1 disjoint cycles in total. Otherwise, the digraph is oriented (has no 2-cycles), and the result follows from the small-overlap cycle packing theorem for arc-dominated oriented graphs.
Adjacency in the common-predecessor graph of D is decidable.
Unfolding the definition of the common-predecessor graph, two distinct vertices are adjacent if and only if they share an in-neighbour in D. Since the vertex set is finite and adjacency in D is decidable, this existential condition is decidable by exhaustive search, which Lean synthesizes automatically.
private instance in478_decadj_digraph_small_overlap_cycle_packing_step {α : Type} [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] : DecidableRel (digraph_common_predecessor_graph D).Adj := by intro u v unfold digraph_common_predecessor_graph infer_instance
If D contains a 2-cycle, then D contains k + 1 vertex-disjoint directed cycles.
We split into cases on whether D contains a 2-cycle, that is, a pair of vertices u and v with edges in both directions. If such a pair exists, the lemma digraph_digon_cycle_packing_step provides k + 1 vertex-disjoint directed cycles: the 2-cycle on {u, v} together with k disjoint cycles obtained from the inductive hypothesis hpack on the remaining vertices, which retain outdegree at least d.
uses
digraph_digon_cycle_packing_stepclassical by_cases h : ∃ u v, D.Adj u v ∧ D.Adj v u · obtain ⟨u,v,huv,hvu⟩ := h exact digraph_digon_cycle_packing_step α D k d hloop hdeg hpack u v huv hvu
If D contains no 2-cycle, then D is oriented.
In the remaining case, no pair of mutually adjacent vertices exists. Therefore, whenever there is an arc from u to v, there cannot be an arc from v to u, as that would form a 2-cycle and contradict the case assumption.
· have hori : ∀ u v, D.Adj u v → ¬ D.Adj v u := by intro u v huv hvu exact h ⟨u,v,huv,hvu⟩
D contains k + 1 vertex-disjoint directed cycles.
With D shown to be oriented, all preconditions of digraph_small_overlap_arc_dominated_cycle_packing_step are satisfied: D is loopless, oriented, arc-dominated, has minimum outdegree at least d + 2, and satisfies the small-overlap bound. Applying this lemma with the inductive packing hypothesis hpack yields k + 1 vertex-disjoint directed cycles.
uses
digraph_small_overlap_arc_dominated_cycle_packing_stepexact digraph_small_overlap_arc_dominated_cycle_packing_step α D k d hloop hori hdeg hdom hsmall hpack
digraph_digon_cycle_packing_step- If a loopless digraph with minimum outdegree at least d+2 contains a 2-cycle, and every induced sub-digraph with minimum outdegree at least d contains k disjoint directed cycles, then the digraph contains k+1 disjoint directed cycles.
digraph_small_overlap_arc_dominated_cycle_packing_step- If a loopless, oriented, arc-dominated digraph with minimum outdegree at least d+2 satisfies the small-overlap condition on common predecessors, and every induced sub-digraph with minimum outdegree at least d contains k disjoint directed cycles, then the digraph contains k+1 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.
private instance in478_decadj_digraph_small_overlap_cycle_packing_step {α : Type} [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] : DecidableRel (digraph_common_predecessor_graph D).Adj := by intro u v unfold digraph_common_predecessor_graph infer_instancetheorem digraph_small_overlap_cycle_packing_step (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (k d : ℕ) (hloop : ∀ v, ¬ D.Adj v v) (hdeg : ∀ v, d + 2 ≤ (Finset.univ.filter fun w => D.Adj v w).card) (hdom : ∀ u v, D.Adj u v → ∃ w, D.Adj w u ∧ D.Adj w v) (hsmall : 3 * ((∑ v : α, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) - (digraph_common_predecessor_graph D).edgeFinset.card) < Fintype.card α) (hpack : ∀ T : Finset α, T.Nonempty → (∀ v ∈ T, d ≤ (T.filter fun w => D.Adj v w).card) → ∃ s : Fin k → Finset α, (∀ i, s i ⊆ T ∧ digraph_directed_cycle_on D (s i)) ∧ Pairwise (fun i j => Disjoint (s i) (s j))) : ∃ s : Fin (k + 1) → Finset α, (∀ i, digraph_directed_cycle_on D (s i)) ∧ Pairwise (fun i j => Disjoint (s i) (s j)) := by classical by_cases h : ∃ u v, D.Adj u v ∧ D.Adj v u · obtain ⟨u,v,huv,hvu⟩ := h exact digraph_digon_cycle_packing_step α D k d hloop hdeg hpack u v huv hvu · have hori : ∀ u v, D.Adj u v → ¬ D.Adj v u := by intro u v huv hvu exact h ⟨u,v,huv,hvu⟩ exact digraph_small_overlap_arc_dominated_cycle_packing_step α D k d hloop hori hdeg hdom hsmall hpack