AFTD Auto-Formalizing Theoretical Domains

digraph_trianglefree_weighted_overlap_cycle_packing_step

theoremverified

For a loopless oriented arc-dominated digraph of directed girth at least four, the k-cycle theorem at outdegree d implies a (k+1)-cycle packing at outdegree d+2 whenever eight times the repeated-pair incidence count plus the number of multiplicity-two pairs is less than three times the order.

Statement

theorem digraph_trianglefree_weighted_overlap_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)
    (hgirth : ∀ C : Finset α, digraph_directed_cycle_on D C → 4 ≤ C.card)
    (hdeg : ∀ v, d + 2 ≤ (Finset.univ.filter fun w => D.Adj v w).card)
    (hdom : ∀ u v, D.Adj u v → ∃ p, D.Adj p u ∧ D.Adj p v)
    (hsmall : 8 * ((∑ v : α, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) -
      (digraph_common_predecessor_graph D).edgeFinset.card) +
      digraph_common_predecessor_double_edges α D < 3 * 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
Triangle-free center budget for the four-cycle campaign; experiments 13471 and 13473.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 8

The proof, explained

The proof finds a good center vertex v whose out-neighborhood is clean (no two out-neighbors share another common predecessor) and self-dominating, via digraph_trianglefree_weighted_good_center. Because the minimum out-degree is at least d + 2 ≥ 2, v has an out-neighbor, which together with self-domination ensures the existence of a directed cycle C contained entirely within the out-neighborhood of v. By arc-domination, v also has an in-neighbor p. Finally, digraph_clean_outneighborhood_cycle_packing_step uses this clean cycle C and the in-neighbor p to extend a k-cycle packing on the remaining vertices into a (k+1)-cycle packing of D.

  1. Adjacency in the common predecessor graph is decidable.

    For any two vertices u and v, unfolding the definition of the common predecessor graph reduces adjacency to checking inequality and the existence of a common predecessor in the finite vertex type, which typeclass inference synthesizes as decidable.

    lines 3–5

      intro u v
      unfold digraph_common_predecessor_graph
      infer_instance
  2. There exists a vertex v with a clean out-neighborhood whose out-neighborhood is self-dominating.

    By digraph_trianglefree_weighted_good_center, the structural hypotheses on D—being loopless, oriented, of directed girth at least four, arc-dominated, and satisfying the weighted overlap bound on common predecessors—guarantee a vertex v such that distinct out-neighbors of v share no common predecessor other than v itself, and every out-neighbor of v has an arc to another out-neighbor of v.

    lines 23–24

    uses digraph_trianglefree_weighted_good_center

      classical
      obtain ⟨v,hclean,hcodom⟩ := digraph_trianglefree_weighted_good_center α D hloop hori hgirth hdom hsmall
  3. The center vertex v has positive out-degree, so it has at least one out-neighbor w.

    The minimum degree hypothesis hdeg implies that the out-degree of v is at least d + 2 ≥ 2 > 0. Since the cardinality of its out-neighborhood is strictly positive, the set is nonempty, yielding an out-neighbor w.

    lines 25–30

    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. The out-neighborhood of v contains a directed cycle C.

    Applying digraph_local_outneighborhood_cycle to the vertex v, using that v has an out-neighbor and that its out-neighborhood is self-dominating, produces a directed cycle C all of whose vertices are out-neighbors of v.

    line 31

    uses digraph_local_outneighborhood_cycle

      obtain ⟨C,hC,hCout⟩ := digraph_local_outneighborhood_cycle α D hloop v hv hcodom
  5. The center vertex v has an in-neighbor p.

    Using the out-neighbor w of v, the arc-domination hypothesis hdom on the directed edge (v, w) provides a vertex p that is a common predecessor of both v and w; in particular, p is adjacent to v.

    lines 32–33

      obtain ⟨w,hw⟩ := hv
      obtain ⟨p,hpv,_⟩ := hdom v w hw
  6. The digraph D contains a packing of k + 1 pairwise disjoint directed cycles.

    The reduction lemma digraph_clean_outneighborhood_cycle_packing_step combines the cycle C in the clean out-neighborhood of v, the in-neighbor p of v, and the induction hypothesis hpack to produce k + 1 pairwise vertex-disjoint directed cycles in D.

    lines 34–35

    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
Finset.card_pos.mp
A finite set with strictly positive cardinality has at least one element.
Finset.mem_filter.mp
An element belongs to a filtered finset if and only if it belongs to the base finset and satisfies the filter condition.
digraph_trianglefree_weighted_good_center
In a loopless oriented arc-dominated digraph of directed girth at least four satisfying the weighted common-predecessor overlap bound, there exists a vertex v with a clean out-neighborhood (no two distinct out-neighbors share any other common predecessor) such that every out-neighbor has an out-edge staying in N⁺(v).
digraph_local_outneighborhood_cycle
In a loopless digraph, if a vertex v has positive out-degree and every out-neighbor has an out-edge to another out-neighbor of v, then the out-neighborhood of v contains a directed cycle.
digraph_clean_outneighborhood_cycle_packing_step
In a loopless oriented digraph of minimum out-degree at least d + 2, if a vertex v has an in-neighbor, a clean out-neighborhood, and contains a directed cycle C within its out-neighborhood, then a k-cycle packing result at minimum out-degree d extends to a (k+1)-cycle packing in the whole digraph.

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 in516_weighted_pack_decAdj {α : 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_trianglefree_weighted_overlap_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)    (hgirth : ∀ C : Finset α, digraph_directed_cycle_on D C → 4 ≤ C.card)    (hdeg : ∀ v, d + 2 ≤ (Finset.univ.filter fun w => D.Adj v w).card)    (hdom : ∀ u v, D.Adj u v → ∃ p, D.Adj p u ∧ D.Adj p v)    (hsmall : 8 * ((∑ v : α, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) -      (digraph_common_predecessor_graph D).edgeFinset.card) +      digraph_common_predecessor_double_edges α D < 3 * 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_trianglefree_weighted_good_center α D hloop hori hgirth 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