AFTD Auto-Formalizing Theoretical Domains

digraph_trianglefree_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_trianglefree_weighted_good_center
    (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj]
    (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)
    (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 α) :
    ∃ 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 theorem shows that an oriented, loopless, arc-dominated digraph of girth at least 4 has a vertex with a clean out-neighborhood and common successors along each outgoing arc. Using the arc-domination hypothesis, each directed edge is mapped to a predecessor arc dominating it. A weighted counting lemma bounds three times the number of dirty vertices and missing arcs by the weighted common predecessor expression, which by assumption is strictly less than 3 * |α|, allowing a budget-transfer theorem to guarantee the existence of such a center vertex.

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

    To construct the edge set of the common predecessor graph as a finite set, we establish decidability of adjacency between any vertices u and v. Unfolding the definition of digraph_common_predecessor_graph shows that adjacency is a bounded existential query over the finite type α, which Lean's typeclass resolution synthesizes automatically.

    lines 3–5

      intro u v
      unfold digraph_common_predecessor_graph
      infer_instance
  2. Every directed edge u → v has an assigned predecessor dominating the edge, satisfying choose(u, v) → u and choose(u, v) → v.

    Using classical choice on the arc-domination hypothesis hdom, we define a function choose that selects for each arc u → v a vertex dominating that arc. The lemma Classical.choose_spec establishes that this choice satisfies both choose(u, v) → u and choose(u, v) → v.

    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. The arc subtype, the predecessor arc map f, the set of dirty vertices, and the set of missing arcs are defined.

    We define Arc as the subtype of directed edges and f : Arc → Arc sending each edge (u, v) to (choose(u, v), u). A vertex is defined to be dirty if two of its out-neighbors share another common predecessor. The set missing consists of all arcs not belonging to 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. Three times the sum of the number of dirty vertices and missing arcs is bounded by the weighted common-predecessor expression.

    The lemma digraph_trianglefree_arc_map_weighted_budget applies to loopless oriented digraphs of girth at least 4, establishing that 3 * (|dirty| + |missing|) is at most 8 * (∑_v (d⁺(v) choose 2) - |E(G_cp)|) + |E_2(G_cp)|.

    line 28

    uses digraph_trianglefree_arc_map_weighted_budget

      have hw := digraph_trianglefree_arc_map_weighted_budget α D choose hloop hori hgirth hchoice
  5. The total number of dirty vertices and missing arcs is strictly less than the total number of vertices, |dirty| + |missing| < |α|. automation

    Hypothesis hsmall states that the weighted bound is strictly less than 3 * |α|. Combining this with the weighted budget inequality 3 * (|dirty| + |missing|) ≤ RHS via linear integer arithmetic (omega) derives |dirty| + |missing| < |α|.

    lines 29–31

      have hb : dirty.card + missing.card < Fintype.card α := by
        change 3 * (dirty.card + missing.card) ≤ _ at hw
        omega
  6. There exists a vertex with a clean out-neighborhood whose outgoing arcs each share a common successor.

    Applying digraph_good_center_from_arc_map_budget with the verified budget |dirty| + |missing| < |α| yields a vertex v whose out-neighborhood contains no pairs with an outside common predecessor and such that every out-neighbor w shares a common successor with v.

    line 32

    uses digraph_good_center_from_arc_map_budget

      exact digraph_good_center_from_arc_map_budget α D choose hchoice hb
Classical.choose_spec
Given an existential proof ∃ x, p x, the witness Classical.choose satisfies p.
digraph_trianglefree_arc_map_weighted_budget
For a finite loopless oriented digraph of directed girth at least 4 with a dominating predecessor chosen for each arc, three times the number of dirty vertices plus missing arcs is at most 8 times the difference between the sum of pairs of out-neighbors and the common predecessor edges, plus the number of double edges.
digraph_good_center_from_arc_map_budget
If the sum of dirty vertices and arcs missing from the image of an arc-dominating map is strictly less than the total number of vertices, then the digraph contains a vertex with a clean out-neighborhood 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_trianglefree_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_trianglefree_weighted_good_center    (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj]    (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)    (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 α) :    ∃ 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_trianglefree_arc_map_weighted_budget α D choose hloop hori hgirth hchoice  have hb : dirty.card + missing.card < Fintype.card α := by    change 3 * (dirty.card + missing.card) ≤ _ at hw    omega  exact digraph_good_center_from_arc_map_budget α D choose hchoice hb
See it in the graphDiscuss this resultChallenge it