AFTD Auto-Formalizing Theoretical Domains

digraph_linear_arc_dominated_cycle_packing_step

theoremverified

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

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.

  1. 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.

    lines 16–17

    uses Classical.choice

      classical
      let v : α := Classical.choice ‹Nonempty α›
  2. 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).

    lines 18–23

    uses Finset.card_pos.mp, Finset.mem_filter.mp

      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⟩
  3. 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.

    lines 24–26

    uses ExistsUnique.exists, digraph_linear_arc_dominated_unique_common_successor

      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)
  4. 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.

    line 27

    uses digraph_local_outneighborhood_cycle

      obtain ⟨C, hC, hCout⟩ := digraph_local_outneighborhood_cycle α D hloop v hv hc
  5. The 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.

    lines 28–29

      obtain ⟨w, hw⟩ := hv
      obtain ⟨p, hpv, hpw⟩ := hdom v w hw
  6. 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.

    lines 30–33

      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
  7. 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.

    line 34

    uses digraph_clean_outneighborhood_cycle_packing_step

      exact 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

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
See it in the graphDiscuss this resultChallenge it