AFTD Auto-Formalizing Theoretical Domains

digraph_small_overlap_arc_dominated_cycle_packing_step

theoremverified

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

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.

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

    lines 2–4

      intro u v
      unfold digraph_common_predecessor_graph
      infer_instance
  2. 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).

    lines 20–21

    uses digraph_oriented_small_overlap_good_center

      classical
      obtain ⟨v,hclean,hcodom⟩ := digraph_oriented_small_overlap_good_center α D hloop hori hdom hsmall
  3. The 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.

    lines 22–27

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

    line 28

    uses digraph_local_outneighborhood_cycle

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

    lines 29–30

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

    lines 31–32

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

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