AFTD Auto-Formalizing Theoretical Domains

op_1355_claw_neighborhood_sum_upper_bound

theoremverified

The closed-neighborhood activity sum at the center is at most 31+1/16 for the explicit embedded-claw profile.

Statement

open scoped Classical BigOperators in
theorem op_1355_claw_neighborhood_sum_upper_bound
    {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (c u v w : V)
    (hadj : G.Adj c u ∧ G.Adj c v ∧ G.Adj c w)
    (hdist : u ≠ v ∧ u ≠ w ∧ v ≠ w)
    (hnon : ¬ G.Adj u v ∧ ¬ G.Adj u w ∧ ¬ G.Adj v w)
    (lam : V → ℝ)
    (hlam : ∀ x, lam x = if x = c then 1 else if x = u ∨ x = v ∨ x = w then 10 else 1 / (16 * (2 : ℝ) ^ Fintype.card V)) :
    (∑ x ∈ insert c (G.neighborFinset c), lam x) ≤ (31 : ℝ) + 1 / 16
Source
OP-1355, explicit induced-claw witness for necessity
Verified
15 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1
  • op_1355_claw_free_of_weighted_boundIf a finite simple graph G on a finite type V with decidable equality satisfies the weighted hard-core closed-neighborhood variance bound…

The proof, explained

The proof partitions the closed neighborhood S = {c} ∪ N(c) of the claw center c into the four claw vertices B = {c, u, v, w} and the remaining neighbors S \ B. Because c is adjacent to u, v, w and all four vertices are distinct, the sum of λ over B evaluates exactly to 1 + 10 + 10 + 10 = 31. On the remaining vertices in S \ B, each vertex has the small activity 1 / (16 * 2^|V|), giving a sum bounded by |V| * (1 / (16 * 2^|V|)) ≤ 1/16 using |V| ≤ 2^|V|. Combining these two contributions yields the upper bound 31 + 1/16.

  1. Define the closed neighborhood S and claw vertex set B, and establish that c, u, v, w are pairwise distinct.

    We define S = {c} ∪ N(c) for the closed neighborhood of c, and B = {c, u, v, w} for the vertices of the claw. Since c is adjacent to u, v, and w in the simple graph G (which has no self-loops), c cannot equal u, v, or w. Combining this with the hypothesis hdist that u, v, w are pairwise distinct ensures that all four vertices in B are distinct.

    lines 11–22

      classical
      set S := insert c (G.neighborFinset c) with hS
      set B : Finset V := {c, u, v, w} with hB
      have hcu : c ≠ u := hadj.1.ne
      have hcv : c ≠ v := hadj.2.1.ne
      have hcw : c ≠ w := hadj.2.2.ne
      have huc : u ≠ c := hadj.1.ne'
      have hvc : v ≠ c := hadj.2.1.ne'
      have hwc : w ≠ c := hadj.2.2.ne'
      have huv : u ≠ v := hdist.1
      have huw : u ≠ w := hdist.2.1
      have hvw : v ≠ w := hdist.2.2
  2. B is a subset of S.

    For any vertex x ∈ B = {c, u, v, w}, either x = c (which is in S by definition), or x is one of u, v, w, in which case x is adjacent to c and hence lies in the neighborhood N(c) ⊆ S.

    lines 23–32

    uses Finset.mem_insert, Finset.mem_singleton, SimpleGraph.mem_neighborFinset

      have hBsub : B ⊆ S := by
        intro x hx
        rw [hB] at hx
        rw [hS]
        simp only [Finset.mem_insert, Finset.mem_singleton] at hx ⊢
        rcases hx with hxc | hxu | hxv | hxw
        · exact Or.inl hxc
        · exact Or.inr (hxu.symm ▸ (SimpleGraph.mem_neighborFinset G c u).mpr hadj.1)
        · exact Or.inr (hxv.symm ▸ (SimpleGraph.mem_neighborFinset G c v).mpr hadj.2.1)
        · exact Or.inr (hxw.symm ▸ (SimpleGraph.mem_neighborFinset G c w).mpr hadj.2.2)
  3. The activity values on B are λ(c) = 1 and λ(u) = λ(v) = λ(w) = 10.

    Evaluating the piecewise definition of λ at c triggers the first branch, giving 1. At u, v, and w, each vertex is distinct from c, which bypasses the first branch and satisfies the second condition x ∈ {u, v, w}, resulting in the value 10 for each.

    lines 33–36

      have hlamc : lam c = 1 := by rw [hlam c]; simp
      have hlamu : lam u = 10 := by rw [hlam u]; simp [huc]
      have hlamv : lam v = 10 := by rw [hlam v]; simp [hvc]
      have hlamw : lam w = 10 := by rw [hlam w]; simp [hwc]
  4. The sum of λ over B equals 31.

    Because the four vertices c, u, v, w are pairwise distinct, the finite set sum over B decomposes into the sum of the four individual values λ(c) + λ(u) + λ(v) + λ(w) = 1 + 10 + 10 + 10 = 31.

    lines 37–44

    uses Finset.sum_insert, Finset.sum_singleton

      have hsumB : ∑ x ∈ B, lam x = 31 := by
        rw [hB]
        rw [Finset.sum_insert (by simp [hcu, hcv, hcw])]
        rw [Finset.sum_insert (by simp [huv, huw])]
        rw [Finset.sum_insert (by simp [hvw])]
        rw [Finset.sum_singleton]
        rw [hlamc, hlamu, hlamv, hlamw]
        norm_num
  5. For every vertex x ∈ S \ B, λ(x) = 1 / (16 * 2^|V|).

    Any vertex x in the difference S \ B does not belong to B, so x ≠ c, x ≠ u, x ≠ v, and x ≠ w. Consequently, evaluating λ(x) bypasses both the c branch and the {u, v, w} branch, falling into the default branch.

    lines 45–53

    uses Finset.mem_sdiff, Finset.mem_insert, Finset.mem_singleton, not_or

      have hsmall : ∀ x ∈ S \ B, lam x = 1 / (16 * (2:ℝ) ^ Fintype.card V) := by
        intro x hx
        rw [Finset.mem_sdiff] at hx
        obtain ⟨hxS, hxB⟩ := hx
        rw [hB] at hxB
        simp only [Finset.mem_insert, Finset.mem_singleton, not_or] at hxB
        obtain ⟨hxc, hxu, hxv, hxw⟩ := hxB
        rw [hlam x]
        simp [hxc, hxu, hxv, hxw]
  6. The sum of λ over S \ B is at most |V| * (1 / (16 * 2^|V|)).

    Since λ is constant on S \ B, the sum equals |S \ B| * (1 / (16 * 2^|V|)). Bounding the size of S \ B by the total number of vertices |V| yields the upper bound.

    lines 54–61

    uses Finset.sum_congr, Finset.sum_const, nsmul_eq_mul, mul_le_mul_of_nonneg_right, Finset.card_le_univ

      have hstep7 : ∑ x ∈ S \ B, lam x ≤ (Fintype.card V : ℝ) * (1 / (16 * (2:ℝ) ^ Fintype.card V)) := by
        have hcongr : ∑ x ∈ S \ B, lam x = ∑ x ∈ S \ B, (1 / (16 * (2:ℝ) ^ Fintype.card V)) := by
          apply Finset.sum_congr rfl
          intro x hx
          exact hsmall x hx
        rw [hcongr, Finset.sum_const, nsmul_eq_mul]
        apply mul_le_mul_of_nonneg_right _ (by positivity)
        exact_mod_cast Finset.card_le_univ (S \ B)
  7. |V| * (1 / (16 * 2^|V|)) ≤ 1/16.

    By the standard inequality n < 2^n for natural numbers, we have |V| ≤ 2^|V| in the reals. Multiplying both sides by the positive factor 1 / (16 * 2^|V|) gives at most 2^|V| * (1 / (16 * 2^|V|)) = 1/16.

    lines 62–71

    uses Nat.lt_two_pow_self, Nat.cast_le, Nat.cast_pow, mul_le_mul_of_nonneg_right, le_of_lt

      have hfinal : (Fintype.card V : ℝ) * (1 / (16 * (2:ℝ) ^ Fintype.card V)) ≤ 1/16 := by
        have hnlt_nat : Fintype.card V ≤ 2 ^ Fintype.card V := (Nat.lt_two_pow_self).le
        have hnlt : (Fintype.card V : ℝ) ≤ (2:ℝ) ^ Fintype.card V := by
          have := Nat.cast_le (α := ℝ).mpr hnlt_nat
          rwa [Nat.cast_pow] at this
        have hpos : (0:ℝ) < 1 / (16 * (2:ℝ) ^ Fintype.card V) := by positivity
        calc (Fintype.card V : ℝ) * (1 / (16 * (2:ℝ) ^ Fintype.card V))
            ≤ (2:ℝ) ^ Fintype.card V * (1 / (16 * (2:ℝ) ^ Fintype.card V)) :=
              mul_le_mul_of_nonneg_right hnlt (le_of_lt hpos)
          _ = 1/16 := by field_simp
  8. The total neighborhood sum of λ over S is at most 31 + 1/16.

    Because B ⊆ S, the sum over S splits into the sum over S \ B plus the sum over B. Substituting the value 31 for B and the bound 1/16 for S \ B gives at most 31 + 1/16.

    lines 72–77

    uses Finset.sum_sdiff

      calc ∑ x ∈ S, lam x
          = ∑ x ∈ S \ B, lam x + ∑ x ∈ B, lam x := (Finset.sum_sdiff hBsub).symm
        _ = ∑ x ∈ S \ B, lam x + 31 := by rw [hsumB]
        _ ≤ (Fintype.card V : ℝ) * (1 / (16 * (2:ℝ) ^ Fintype.card V)) + 31 := by linarith [hstep7]
        _ ≤ 1/16 + 31 := by linarith [hfinal]
        _ = 31 + 1/16 := by ring
Finset.card_le_univ
The cardinality of any finite subset of a finite type is at most the cardinality of the whole type.
Finset.mem_insert
An element is in insert a s if and only if it equals a or is in s.
Finset.mem_sdiff
An element is in the set difference s \ t if and only if it is in s and not in t.
Finset.mem_singleton
An element is in {a} if and only if it equals a.
Finset.sum_congr
Two sums over finite sets are equal if the index sets are equal and the summands agree on every element.
Finset.sum_const
The sum of a constant value over a finite set equals the cardinality of the set times the constant.
Finset.sum_insert
If a ∉ s, the sum of a function over insert a s equals its value at a plus its sum over s.
Finset.sum_sdiff
For a subset s₁ ⊆ s₂, the sum over s₂ equals the sum over s₂ \ s₁ plus the sum over s₁.
Finset.sum_singleton
The sum of a function over a singleton set {a} equals the function evaluated at a.
le_of_lt
A strict inequality a < b implies the weak inequality a ≤ b.
mul_le_mul_of_nonneg_right
If b ≤ c and a ≥ 0, then b * a ≤ c * a.
Nat.cast_le
For natural numbers m and n, m ≤ n if and only if their casts to an ordered semiring satisfy ↑m ≤ ↑n.
Nat.cast_pow
The cast of a power of natural numbers m^n into a semiring equals (↑m)^n.
Nat.lt_two_pow_self
For every natural number n, n < 2^n.
not_or
The negation ¬(p ∨ q) is logically equivalent to ¬p ∧ ¬q.
nsmul_eq_mul
Natural scalar multiplication n • a in a semiring equals the product of the cast of n with a.
SimpleGraph.mem_neighborFinset
A vertex w is in the neighbor finset of v if and only if v and w are adjacent in the graph.

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

open scoped Classical BigOperators intheorem op_1355_claw_neighborhood_sum_upper_bound    {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (c u v w : V)    (hadj : G.Adj c u ∧ G.Adj c v ∧ G.Adj c w)    (hdist : u ≠ v ∧ u ≠ w ∧ v ≠ w)    (hnon : ¬ G.Adj u v ∧ ¬ G.Adj u w ∧ ¬ G.Adj v w)    (lam : V → ℝ)    (hlam : ∀ x, lam x = if x = c then 1 else if x = u ∨ x = v ∨ x = w then 10 else 1 / (16 * (2 : ℝ) ^ Fintype.card V)) :    (∑ x ∈ insert c (G.neighborFinset c), lam x) ≤ (31 : ℝ) + 1 / 16 := by  classical  set S := insert c (G.neighborFinset c) with hS  set B : Finset V := {c, u, v, w} with hB  have hcu : c ≠ u := hadj.1.ne  have hcv : c ≠ v := hadj.2.1.ne  have hcw : c ≠ w := hadj.2.2.ne  have huc : u ≠ c := hadj.1.ne'  have hvc : v ≠ c := hadj.2.1.ne'  have hwc : w ≠ c := hadj.2.2.ne'  have huv : u ≠ v := hdist.1  have huw : u ≠ w := hdist.2.1  have hvw : v ≠ w := hdist.2.2  have hBsub : B ⊆ S := by    intro x hx    rw [hB] at hx    rw [hS]    simp only [Finset.mem_insert, Finset.mem_singleton] at hx ⊢    rcases hx with hxc | hxu | hxv | hxw    · exact Or.inl hxc    · exact Or.inr (hxu.symm ▸ (SimpleGraph.mem_neighborFinset G c u).mpr hadj.1)    · exact Or.inr (hxv.symm ▸ (SimpleGraph.mem_neighborFinset G c v).mpr hadj.2.1)    · exact Or.inr (hxw.symm ▸ (SimpleGraph.mem_neighborFinset G c w).mpr hadj.2.2)  have hlamc : lam c = 1 := by rw [hlam c]; simp  have hlamu : lam u = 10 := by rw [hlam u]; simp [huc]  have hlamv : lam v = 10 := by rw [hlam v]; simp [hvc]  have hlamw : lam w = 10 := by rw [hlam w]; simp [hwc]  have hsumB : ∑ x ∈ B, lam x = 31 := by    rw [hB]    rw [Finset.sum_insert (by simp [hcu, hcv, hcw])]    rw [Finset.sum_insert (by simp [huv, huw])]    rw [Finset.sum_insert (by simp [hvw])]    rw [Finset.sum_singleton]    rw [hlamc, hlamu, hlamv, hlamw]    norm_num  have hsmall : ∀ x ∈ S \ B, lam x = 1 / (16 * (2:ℝ) ^ Fintype.card V) := by    intro x hx    rw [Finset.mem_sdiff] at hx    obtain ⟨hxS, hxB⟩ := hx    rw [hB] at hxB    simp only [Finset.mem_insert, Finset.mem_singleton, not_or] at hxB    obtain ⟨hxc, hxu, hxv, hxw⟩ := hxB    rw [hlam x]    simp [hxc, hxu, hxv, hxw]  have hstep7 : ∑ x ∈ S \ B, lam x ≤ (Fintype.card V : ℝ) * (1 / (16 * (2:ℝ) ^ Fintype.card V)) := by    have hcongr : ∑ x ∈ S \ B, lam x = ∑ x ∈ S \ B, (1 / (16 * (2:ℝ) ^ Fintype.card V)) := by      apply Finset.sum_congr rfl      intro x hx      exact hsmall x hx    rw [hcongr, Finset.sum_const, nsmul_eq_mul]    apply mul_le_mul_of_nonneg_right _ (by positivity)    exact_mod_cast Finset.card_le_univ (S \ B)  have hfinal : (Fintype.card V : ℝ) * (1 / (16 * (2:ℝ) ^ Fintype.card V)) ≤ 1/16 := by    have hnlt_nat : Fintype.card V ≤ 2 ^ Fintype.card V := (Nat.lt_two_pow_self).le    have hnlt : (Fintype.card V : ℝ) ≤ (2:ℝ) ^ Fintype.card V := by      have := Nat.cast_le (α := ℝ).mpr hnlt_nat      rwa [Nat.cast_pow] at this    have hpos : (0:ℝ) < 1 / (16 * (2:ℝ) ^ Fintype.card V) := by positivity    calc (Fintype.card V : ℝ) * (1 / (16 * (2:ℝ) ^ Fintype.card V))        ≤ (2:ℝ) ^ Fintype.card V * (1 / (16 * (2:ℝ) ^ Fintype.card V)) :=          mul_le_mul_of_nonneg_right hnlt (le_of_lt hpos)      _ = 1/16 := by field_simp  calc ∑ x ∈ S, lam x      = ∑ x ∈ S \ B, lam x + ∑ x ∈ B, lam x := (Finset.sum_sdiff hBsub).symm    _ = ∑ x ∈ S \ B, lam x + 31 := by rw [hsumB]    _ ≤ (Fintype.card V : ℝ) * (1 / (16 * (2:ℝ) ^ Fintype.card V)) + 31 := by linarith [hstep7]    _ ≤ 1/16 + 31 := by linarith [hfinal]    _ = 31 + 1/16 := by ring
See it in the graphDiscuss this resultChallenge it