digraph_linear_arc_dominated_cycle_packing_step
The k-cycle theorem at outdegree d implies the (k+1)-cycle theorem at outdegree d+2 for oriented linear arc-dominated digraphs.
Statement
theorem digraph_linear_arc_dominated_cycle_packing_step (α : Type) [Fintype α] [DecidableEq α] [Nonempty α] (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) (hlinear : ∀ u v, u ≠ v → ∀ a b, D.Adj a u → D.Adj a v → D.Adj b u → D.Adj b v → a = b) (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 zero-overlap packing induction for OP-110 and the corresponding k-cycle problem.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- digraph_linear_arc_dominated_unique_common_successorEvery arc of a finite loopless linear arc-dominated digraph has exactly one common successor; regularity and orientation are not required.
- 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.
The proof, explained
The proof reduces the cycle-packing induction step to an existing theorem, digraph_clean_outneighborhood_cycle_packing_step, by verifying its geometric prerequisites at an arbitrary vertex v. Arc-domination and linearity ensure that every out-neighbor of v shares an out-neighbor with v, which yields a directed cycle C contained entirely within the out-neighborhood of v. In addition, arc-domination provides an in-neighbor p of v, and linearity ensures that no two distinct out-neighbors of v share any in-neighbor other than v. Applying the reduction theorem then combines C with k disjoint cycles obtained from the packing hypothesis to produce k + 1 pairwise disjoint directed cycles.
We choose an arbitrary vertex v from the nonempty vertex set α.
Because the vertex type α is assumed to be nonempty, the axiom of choice via Classical.choice provides a base vertex v.
uses
Classical.choiceclassical let v : α := Classical.choice ‹Nonempty α›The vertex v has at least one out-neighbor.
The minimum outdegree hypothesis hdeg guarantees that the outdegree of v is at least d + 2 ≥ 2 > 0. By Finset.card_pos.mp, the out-neighborhood of v is nonempty, yielding a vertex w such that v → w (via Finset.mem_filter.mp).
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⟩
Every out-neighbor of v shares a common out-neighbor with v.
For each out-neighbor w of v, the digraph is loopless, arc-dominated, and linear. The lemma digraph_linear_arc_dominated_unique_common_successor shows that the edge v → w has a unique common successor x (satisfying v → x and w → x), whose existence is extracted using ExistsUnique.exists.
uses
ExistsUnique.exists,digraph_linear_arc_dominated_unique_common_successorhave hc : ∀ w, D.Adj v w → ∃ x, D.Adj v x ∧ D.Adj w x := by intro w hw exact ExistsUnique.exists (digraph_linear_arc_dominated_unique_common_successor α D hloop hdom hlinear v w hw)
There is a directed cycle C contained entirely within the out-neighborhood of v.
Since v has an out-neighbor and every out-neighbor of v has an edge to another out-neighbor of v, digraph_local_outneighborhood_cycle produces a directed cycle C whose vertices all lie in the out-neighborhood of v.
uses
digraph_local_outneighborhood_cycleobtain ⟨C, hC, hCout⟩ := digraph_local_outneighborhood_cycle α D hloop v hv hcThe vertex v has an in-neighbor p.
Taking an out-neighbor w of v, the arc-domination hypothesis hdom applied to the edge v → w provides a common predecessor p such that p → v and p → w, so in particular p is an in-neighbor of v.
obtain ⟨w, hw⟩ := hv obtain ⟨p, hpv, hpw⟩ := hdom v w hw
The out-neighborhood of v is clean: distinct out-neighbors of v share no in-neighbor other than v.
If a and b are distinct out-neighbors of v and some vertex x is also an in-neighbor of both a and b, then both x and v are common in-neighbors of a and b. By the linearity hypothesis hlinear, two distinct vertices share at most one in-neighbor, which forces x = v.
have hclean : ∀ a b, a ≠ b → D.Adj v a → D.Adj v b → ∀ x, D.Adj x a → D.Adj x b → x = v := by intro a b hab hva hvb x hxa hxb exact hlinear a b hab x v hxa hxb hva hvb
There exist k + 1 pairwise disjoint directed cycles in the digraph D.
With a directed cycle C in the out-neighborhood of v, an in-neighbor p of v, and the clean out-neighborhood property verified, applying digraph_clean_outneighborhood_cycle_packing_step with the induction hypothesis hpack completes the induction step.
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
Classical.choice- Given a proof that a type is nonempty, selects an element of that type.
Finset.card_pos.mp- A finite set has cardinality strictly greater than zero if and only if it is nonempty.
Finset.mem_filter.mp- An element belongs to the filtered subset of a finite set if and only if it belongs to the set and satisfies the predicate.
ExistsUnique.exists- Extracts an existential assertion from a unique existence assertion.
digraph_linear_arc_dominated_unique_common_successor- In a loopless, arc-dominated, linear digraph, every directed edge u → v has a unique common successor w satisfying u → w and v → w.
digraph_local_outneighborhood_cycle- In a loopless digraph, if a vertex v has an out-neighbor and every out-neighbor of v has an edge to another out-neighbor of v, then there is a directed cycle whose vertices all lie in the out-neighborhood of v.
digraph_clean_outneighborhood_cycle_packing_step- In an oriented loopless digraph with minimum outdegree at least d + 2, if a vertex v has an in-neighbor, a clean out-neighborhood, and a directed cycle C in its out-neighborhood, and if every nonempty induced subgraph of minimum outdegree at least d packs k disjoint cycles, then the whole digraph packs k + 1 disjoint 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_linear_arc_dominated_cycle_packing_step (α : Type) [Fintype α] [DecidableEq α] [Nonempty α] (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) (hlinear : ∀ u v, u ≠ v → ∀ a b, D.Adj a u → D.Adj a v → D.Adj b u → D.Adj b v → a = b) (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 let v : α := Classical.choice ‹Nonempty α› 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⟩ have hc : ∀ w, D.Adj v w → ∃ x, D.Adj v x ∧ D.Adj w x := by intro w hw exact ExistsUnique.exists (digraph_linear_arc_dominated_unique_common_successor α D hloop hdom hlinear v w hw) obtain ⟨C, hC, hCout⟩ := digraph_local_outneighborhood_cycle α D hloop v hv hc obtain ⟨w, hw⟩ := hv obtain ⟨p, hpv, hpw⟩ := hdom v w hw have hclean : ∀ a b, a ≠ b → D.Adj v a → D.Adj v b → ∀ x, D.Adj x a → D.Adj x b → x = v := by intro a b hab hva hvb x hxa hxb exact hlinear a b hab x v hxa hxb hva hvb exact digraph_clean_outneighborhood_cycle_packing_step α D k d hloop hori hdeg hpack v C hC hCout hclean p hpv