AFTD Auto-Formalizing Theoretical Domains

digraph_small_overlap_cycle_packing_step

theoremverified

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
Used by 3

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.

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

    lines 1–4

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

    lines 19–22

    uses digraph_digon_cycle_packing_step

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

    lines 23–25

      · have hori : ∀ u v, D.Adj u v → ¬ D.Adj v u := by
          intro u v huv hvu
          exact h ⟨u,v,huv,hvu⟩
  4. 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.

    line 26

    uses digraph_small_overlap_arc_dominated_cycle_packing_step

        exact 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

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