AFTD Auto-Formalizing Theoretical Domains

digraph_girth_weighted_overlap_cycle_packing_step

theoremverified

For a loopless oriented arc-dominated digraph of directed girth at least g, the k-cycle theorem at outdegree d implies a (k+1)-cycle packing at outdegree d+2 under the displayed girth-weighted overlap bound.

Statement

theorem digraph_girth_weighted_overlap_cycle_packing_step
    (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (g k d : ℕ)
    (hg : 3 ≤ g) (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 → g ≤ 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 : 2 * g * ((∑ v : α, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) -
      (digraph_common_predecessor_graph D).edgeFinset.card) +
      digraph_common_predecessor_girth_correction α D g < (g - 1) * 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
Girth-dependent center budget for the four-cycle campaign; experiment 13474.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 8

The proof, explained

The proof deduces the (k+1)-cycle packing from the k-cycle packing hypothesis by finding a local directed cycle inside the out-neighborhood of a carefully chosen center vertex. The girth-weighted overlap bound guarantees the existence of a good center vertex v whose out-neighborhood is clean and satisfies a codomain condition. That codomain condition provides a directed cycle C contained entirely in the out-neighborhood of v, while arc-domination provides an in-neighbor p of v. Finally, digraph_clean_outneighborhood_cycle_packing_step removes C and applies the packing hypothesis on the remaining vertices to obtain k + 1 pairwise disjoint directed cycles.

  1. Adjacency in the common predecessor graph of D is decidable. automation

    For any two vertices u and v, the definition of digraph_common_predecessor_graph is unfolded to the assertion that u ≠ v and there exists a common in-neighbor w to u and v in D. Because the vertex type α is finite and adjacency in D is decidable, typeclass synthesis (infer_instance) automatically produces the decision procedure.

    lines 3–5

      intro u v
      unfold digraph_common_predecessor_graph
      infer_instance
  2. There exists a vertex v with a clean out-neighborhood that satisfies the codomain property.

    Applying digraph_girth_weighted_good_center under the hypotheses that D is loopless (hloop), oriented (hori), arc-dominated (hdom), has directed girth at least g ≥ 3 (hg, hgirth), and satisfies the girth-weighted overlap bound (hsmall), we obtain a vertex v whose out-neighborhood is clean (no two distinct out-neighbors share any predecessor other than v, hclean) and satisfies the codomain property (every out-neighbor w of v shares an out-neighbor with v, hcodom).

    lines 23–25

    uses digraph_girth_weighted_good_center

      classical
      obtain ⟨v, hclean, hcodom⟩ :=
        digraph_girth_weighted_good_center α D g hg hloop hori hgirth hdom hsmall
  3. The vertex v has at least one out-neighbor in D.

    By the minimum out-degree condition hdeg, the out-neighborhood of v has cardinality at least d + 2 ≥ 2 > 0. Via Finset.card_pos.mp, this strictly positive cardinality yields a witness w in the out-neighborhood, and Finset.mem_filter.mp confirms that w is an out-neighbor of v (D.Adj v w).

    lines 26–29

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

      have hv : ∃ w, D.Adj v w := by
        have h := hdeg v
        obtain ⟨w, hw⟩ := Finset.card_pos.mp (show 0 < (Finset.univ.filter fun w => D.Adj v w).card by omega)
        exact ⟨w, (Finset.mem_filter.mp hw).2⟩
  4. There exists a directed cycle C contained entirely within the out-neighborhood of v.

    Because D is loopless (hloop), v has an out-neighbor (hv), and v satisfies the codomain property (hcodom), digraph_local_outneighborhood_cycle guarantees the existence of a directed cycle C such that every vertex in C is an out-neighbor of v (hCout).

    line 30

    uses digraph_local_outneighborhood_cycle

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

    Taking the out-neighbor w of v obtained previously, the arc-domination hypothesis hdom on the directed edge from v to w yields a common predecessor p such that D.Adj p v and D.Adj p w. In particular, p is an in-neighbor of v.

    lines 31–32

      obtain ⟨w, hvw⟩ := hv
      obtain ⟨p, hpv, _⟩ := hdom v w hvw
  6. There exists a packing of k + 1 pairwise disjoint directed cycles in D.

    All hypotheses of digraph_clean_outneighborhood_cycle_packing_step are satisfied: D is loopless and oriented, every vertex has out-degree at least d + 2, the packing hypothesis hpack holds at out-degree d, C is a directed cycle in the out-neighborhood of v, v has a clean out-neighborhood, and p is an in-neighbor of v. Applying this lemma produces k + 1 pairwise disjoint directed cycles in D.

    lines 33–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
digraph_girth_weighted_good_center
In any finite loopless oriented arc-dominated digraph of directed girth at least g ≥ 3 satisfying the girth-weighted overlap bound, there exists a vertex v with a clean out-neighborhood (no two distinct out-neighbors share another common predecessor) that satisfies the codomain property (every out-neighbor shares an out-neighbor with v).
Finset.card_pos.mp
A finite set is non-empty whenever its cardinality is strictly positive.
Finset.mem_filter.mp
If an element belongs to a filtered finite set {x ∈ s | P x}, then it belongs to s and satisfies the predicate P.
digraph_local_outneighborhood_cycle
In a loopless digraph, if a vertex v has at least one out-neighbor and satisfies the codomain property that every out-neighbor shares an out-neighbor with v, then there exists a directed cycle all of whose vertices lie in the out-neighborhood of v.
digraph_clean_outneighborhood_cycle_packing_step
In a loopless oriented digraph where every vertex has out-degree at least d + 2, if every non-empty induced subgraph with minimum out-degree at least d contains k disjoint directed cycles, and there exists a vertex v with a clean out-neighborhood containing a directed cycle C and an in-neighbor p of v, then the 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 in516_girth_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_girth_weighted_overlap_cycle_packing_step    (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (g k d : ℕ)    (hg : 3 ≤ g) (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 → g ≤ 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 : 2 * g * ((∑ v : α, Nat.choose (Finset.univ.filter fun w => D.Adj v w).card 2) -      (digraph_common_predecessor_graph D).edgeFinset.card) +      digraph_common_predecessor_girth_correction α D g < (g - 1) * 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_girth_weighted_good_center α D g hg hloop hori hgirth hdom hsmall  have hv : ∃ w, D.Adj v w := by    have h := hdeg v    obtain ⟨w, hw⟩ := Finset.card_pos.mp (show 0 < (Finset.univ.filter fun w => D.Adj v w).card by omega)    exact ⟨w, (Finset.mem_filter.mp hw).2⟩  obtain ⟨C, hC, hCout⟩ := digraph_local_outneighborhood_cycle α D hloop v hv hcodom  obtain ⟨w, hvw⟩ := hv  obtain ⟨p, hpv, _⟩ := hdom v w hvw  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