AFTD Auto-Formalizing Theoretical Domains

digraph_girth_weighted_good_center

theoremverified

Under the displayed weighted overlap condition, a finite loopless oriented arc-dominated digraph of the specified girth has a clean out-neighborhood whose outgoing arcs each have a common successor.

Statement

theorem digraph_girth_weighted_good_center
    (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj]
    (g : ℕ) (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)
    (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 α) :
    ∃ v, (∀ a b, a ≠ b → D.Adj v a → D.Adj v b →
        ∀ p, D.Adj p a → D.Adj p b → p = v) ∧
      (∀ w, D.Adj v w → ∃ x, D.Adj v x ∧ D.Adj w x)
Source
Weighted center route for the four-cycle campaign; experiment 13473.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
Used by 1

The proof, explained

The proof selects a common predecessor for each directed arc to define an arc transition map sending (u, v) to (choose u v, u). A known weighted budget theorem bounds (g - 1) times the sum of 'dirty' vertices and 'missing' arcs by the given overlap and girth correction quantity. Combining this with the hypothesis and dividing out (g - 1) shows that the defect count is strictly less than the total number of vertices. Finally, an existing center existence theorem deduces the desired good center from this strict budget inequality.

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

    By unfolding the definition of digraph_common_predecessor_graph, deciding adjacency between u and v reduces to testing u ≠ v and searching over α for a common predecessor w with D.Adj w u and D.Adj w v, which typeclass inference automatically synthesizes since α is a finite type with decidable equality and adjacency.

    lines 1–5

    private instance in516_girth_center_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_instance
  2. There is a function choose mapping each arc u → v to a common predecessor of u and v.

    Using classical choice on the arc-domination hypothesis hdom, choose u v selects a vertex p such that D.Adj p u and D.Adj p v whenever D.Adj u v holds.

    lines 18–22

    uses Classical.choose_spec

      classical
      let choose : α → α → α := fun u v => if h : D.Adj u v then Classical.choose (hdom u v h) else u
      have hchoice : ∀ u v, D.Adj u v → D.Adj (choose u v) u ∧ D.Adj (choose u v) v := by
        intro u v h
        simpa [choose,h] using Classical.choose_spec (hdom u v h)
  3. Define the arc type Arc, the arc shift map f, the set of dirty vertices, and the set of missing arcs.

    Arc is the subtype of pairs forming directed edges. The map f sends an arc (u, v) to (choose u v, u). The set dirty consists of vertices sharing two distinct out-neighbors with some other vertex, and missing consists of arcs not in the image of f.

    lines 23–27

      let Arc := {e : α × α // D.Adj e.1 e.2}
      let f : Arc → Arc := fun e => ⟨(choose e.val.1 e.val.2,e.val.1),(hchoice _ _ e.property).1⟩
      let dirty : Finset α := Finset.univ.filter fun u =>
        ∃ a b p, a ≠ b ∧ p ≠ u ∧ D.Adj u a ∧ D.Adj u b ∧ D.Adj p a ∧ D.Adj p b
      let missing : Finset Arc := Finset.univ \ Finset.univ.image f
  4. (g - 1) * (|dirty| + |missing|) is bounded by the weighted overlap sum plus the girth correction term.

    Applying digraph_girth_arc_map_weighted_budget with the chosen predecessor function and graph properties yields this inequality directly.

    line 28

    uses digraph_girth_arc_map_weighted_budget

      have hw := digraph_girth_arc_map_weighted_budget α D choose g hg hloop hori hgirth hchoice
  5. The sum of dirty vertices and missing arcs is strictly less than the total number of vertices |α|.

    By transitivity with the hypothesis hsmall, (g - 1) * (|dirty| + |missing|) < (g - 1) * |α|. Dividing both sides by g - 1 using Nat.lt_of_mul_lt_mul_left yields |dirty| + |missing| < |α|.

    lines 29–32

    uses lt_of_le_of_lt, Nat.lt_of_mul_lt_mul_left

      have hb : dirty.card + missing.card < Fintype.card α := by
        change (g - 1) * (dirty.card + missing.card) ≤ _ at hw
        have hlt : (g - 1) * (dirty.card + missing.card) < (g - 1) * Fintype.card α := lt_of_le_of_lt hw hsmall
        exact Nat.lt_of_mul_lt_mul_left hlt
  6. There exists a vertex v with a clean out-neighborhood whose outgoing arcs each have a common successor.

    Applying digraph_good_center_from_arc_map_budget using the established budget inequality |dirty| + |missing| < |α| completes the proof.

    line 33

    uses digraph_good_center_from_arc_map_budget

      exact digraph_good_center_from_arc_map_budget α D choose hchoice hb
Classical.choose_spec
For an existential statement h : ∃ x, p x, the witness Classical.choose h satisfies p.
digraph_girth_arc_map_weighted_budget
In an oriented loopless digraph with girth at least g and a common-predecessor choice function for every arc, (g - 1) times the sum of dirty vertices and missing arcs is bounded above by 2 * g * (∑_v binom(d⁺(v), 2) - |E|) plus the girth correction term.
lt_of_le_of_lt
If a ≤ b and b < c, then a < c.
Nat.lt_of_mul_lt_mul_left
If a * b < a * c for natural numbers, then b < c.
digraph_good_center_from_arc_map_budget
If the sum of dirty vertices and missing arcs is strictly less than the total number of vertices |V|, then there exists a clean vertex whose outgoing arcs each have a common successor.

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_center_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_good_center    (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj]    (g : ℕ) (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)    (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 α) :    ∃ v, (∀ a b, a ≠ b → D.Adj v a → D.Adj v b →        ∀ p, D.Adj p a → D.Adj p b → p = v) ∧      (∀ w, D.Adj v w → ∃ x, D.Adj v x ∧ D.Adj w x) := by  classical  let choose : α → α → α := fun u v => if h : D.Adj u v then Classical.choose (hdom u v h) else u  have hchoice : ∀ u v, D.Adj u v → D.Adj (choose u v) u ∧ D.Adj (choose u v) v := by    intro u v h    simpa [choose,h] using Classical.choose_spec (hdom u v h)  let Arc := {e : α × α // D.Adj e.1 e.2}  let f : Arc → Arc := fun e => ⟨(choose e.val.1 e.val.2,e.val.1),(hchoice _ _ e.property).1⟩  let dirty : Finset α := Finset.univ.filter fun u =>    ∃ a b p, a ≠ b ∧ p ≠ u ∧ D.Adj u a ∧ D.Adj u b ∧ D.Adj p a ∧ D.Adj p b  let missing : Finset Arc := Finset.univ \ Finset.univ.image f  have hw := digraph_girth_arc_map_weighted_budget α D choose g hg hloop hori hgirth hchoice  have hb : dirty.card + missing.card < Fintype.card α := by    change (g - 1) * (dirty.card + missing.card) ≤ _ at hw    have hlt : (g - 1) * (dirty.card + missing.card) < (g - 1) * Fintype.card α := lt_of_le_of_lt hw hsmall    exact Nat.lt_of_mul_lt_mul_left hlt  exact digraph_good_center_from_arc_map_budget α D choose hchoice hb
See it in the graphDiscuss this resultChallenge it