digraph_small_overlap_arc_dominated_cycle_packing_step
The k-cycle theorem at outdegree d implies the (k+1)-cycle theorem for oriented arc-dominated digraphs of minimum outdegree at least d+2 when repeated common-predecessor pair incidences are less than one third of their order.
Statement
theorem digraph_small_overlap_arc_dominated_cycle_packing_step (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (k d : ℕ) (hloop : ∀ v, ¬ D.Adj v v) (hori : ∀ u v, D.Adj u v → ¬ D.Adj v u) (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 5
- digraph_oriented_small_overlap_good_centerIn an oriented arc-dominated digraph, if repeated common-predecessor pair incidences are less than one third of the order, some vertex has…
- digraph_clean_outneighborhood_cycle_packing_stepA directed cycle inside a clean out-neighborhood can be added to any k-cycle packing theorem two outdegree units lower.
- 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_local_outneighborhood_cycleIf an out-neighborhood is nonempty and each of its vertices has an out-neighbor inside it, it contains a directed cycle.
- digraph_common_predecessor_graphThe simple graph joining distinct vertices that have a common in-neighbor in the digraph.
- Used by 1
- digraph_small_overlap_cycle_packing_stepThe k-cycle theorem at outdegree d implies the (k+1)-cycle theorem for loopless arc-dominated digraphs of minimum outdegree at least d+2…
The proof, explained
Under the small overlap and arc domination hypotheses in an oriented digraph, there exists a clean center v whose out-neighbors share no common predecessor other than v and whose out-neighborhood satisfies codomination. Because the minimum outdegree is at least d + 2 ≥ 2, the out-neighborhood of v is nonempty, which by codomination guarantees the existence of a directed cycle C contained entirely within the out-neighborhood of v. Arc domination ensures that v has an in-neighbor p. Finally, the clean out-neighborhood cycle packing step applies the induction hypothesis on the remaining vertices to produce k disjoint cycles disjoint from C, yielding k + 1 pairwise disjoint directed cycles in total.
Adjacency in the common predecessor graph of D is decidable for every pair of vertices.
Given vertices u and v, unfolding the definition of the common predecessor graph shows that adjacency means u ≠ v and there exists a common predecessor w. Since the vertex set is finite and adjacency in D is decidable, typeclass inference automatically synthesizes decidability for this existential predicate.
intro u v unfold digraph_common_predecessor_graph infer_instance
There exists a vertex v that is a clean center and whose out-neighborhood satisfies codomination.
Assuming classical logic, we apply digraph_oriented_small_overlap_good_center. Using the loopless, oriented, arc-dominated, and small overlap hypotheses, this produces a vertex v whose distinct out-neighbors share no in-neighbor other than v (cleanliness), and every out-neighbor w of v has an arc to another out-neighbor of v (codomination).
uses
digraph_oriented_small_overlap_good_centerclassical obtain ⟨v,hclean,hcodom⟩ := digraph_oriented_small_overlap_good_center α D hloop hori hdom hsmallThe clean center v has at least one out-neighbor.
By the minimum outdegree hypothesis hdeg, the outdegree of v is at least d + 2, which is strictly positive (by linear arithmetic via omega). Applying Finset.card_pos.mp shows the out-neighborhood of v is nonempty, and unpacking it with Finset.mem_filter.mp gives an out-neighbor w of v.
uses
Finset.card_pos.mp,Finset.mem_filter.mphave hv : ∃ w, D.Adj v w := by have hp : 0 < (Finset.univ.filter fun w => D.Adj v w).card := by have := hdeg v omega obtain ⟨w,hw⟩ := Finset.card_pos.mp hp exact ⟨w,(Finset.mem_filter.mp hw).2⟩
There exists a directed cycle C contained entirely within the out-neighborhood of v.
Applying digraph_local_outneighborhood_cycle with the loopless condition, the existence of an out-neighbor of v, and the codomination property yields a directed cycle C whose vertices are all out-neighbors of v.
uses
digraph_local_outneighborhood_cycleobtain ⟨C,hC,hCout⟩ := digraph_local_outneighborhood_cycle α D hloop v hv hcodomThere exists a vertex p that is an in-neighbor of v.
Taking an out-neighbor w of v, the arc domination hypothesis hdom applied to the arc v → w guarantees a common predecessor p having arcs to both v and w; in particular, p → v, so p is an in-neighbor of v.
obtain ⟨w,hw⟩ := hv obtain ⟨p,hpv,_⟩ := hdom v w hw
There exist k + 1 pairwise vertex-disjoint directed cycles in D.
We apply digraph_clean_outneighborhood_cycle_packing_step using the clean center v, the cycle C ⊆ N⁺(v), the cleanliness of v, and the in-neighbor p of v. This lemma applies the induction hypothesis hpack to the graph away from C to obtain k disjoint cycles, which together with C form a packing of k + 1 pairwise disjoint directed cycles.
uses
digraph_clean_outneighborhood_cycle_packing_stepexact digraph_clean_outneighborhood_cycle_packing_step α D k d hloop hori hdeg hpack v C hC hCout hclean p hpv
digraph_oriented_small_overlap_good_center- In a finite loopless oriented digraph satisfying arc domination and the small overlap condition, there exists a vertex v that is a clean center (distinct out-neighbors share no in-neighbor other than v) and satisfies codomination (every out-neighbor has an out-edge within the out-neighborhood of v).
Finset.card_pos.mp- If a finite set has strictly positive cardinality, then it is nonempty.
Finset.mem_filter.mp- If an element belongs to a filtered finset, then it belongs to the ambient set and satisfies the filter predicate.
digraph_local_outneighborhood_cycle- In a loopless digraph, if a vertex v has an out-neighbor and its out-neighborhood satisfies codomination, then there exists a directed cycle whose vertices all lie in the out-neighborhood of v.
digraph_clean_outneighborhood_cycle_packing_step- In an oriented digraph of minimum outdegree at least d + 2, if there is a clean center v with an in-neighbor p and a directed cycle C contained in its out-neighborhood, and if every induced subgraph of minimum outdegree at least d contains k disjoint cycles, then the whole digraph contains k + 1 pairwise disjoint directed cycles.
- The initial lines 1–4 are a formal prerequisite establishing decidability of adjacency in the common predecessor graph, which Lean requires to define its edge finset in the theorem's hypotheses.
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_arc_dominated_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_arc_dominated_cycle_packing_step (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (k d : ℕ) (hloop : ∀ v, ¬ D.Adj v v) (hori : ∀ u v, D.Adj u v → ¬ D.Adj v u) (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 obtain ⟨v,hclean,hcodom⟩ := digraph_oriented_small_overlap_good_center α D hloop hori hdom hsmall have hv : ∃ w, D.Adj v w := by have hp : 0 < (Finset.univ.filter fun w => D.Adj v w).card := by have := hdeg v omega obtain ⟨w,hw⟩ := Finset.card_pos.mp hp exact ⟨w,(Finset.mem_filter.mp hw).2⟩ obtain ⟨C,hC,hCout⟩ := digraph_local_outneighborhood_cycle α D hloop v hv hcodom obtain ⟨w,hw⟩ := hv obtain ⟨p,hpv,_⟩ := hdom v w hw exact digraph_clean_outneighborhood_cycle_packing_step α D k d hloop hori hdeg hpack v C hC hCout hclean p hpv