AFTD Auto-Formalizing Theoretical Domains

simple_graph_triangle_free_weighted_low_neighborhood

theoremverified

In any finite triangle-free graph with nonnegative integer vertex weights, if some vertex has positive weight then some positive-weight vertex has at most half of the total weight in its neighborhood.

Statement

theorem simple_graph_triangle_free_weighted_low_neighborhood {α : Type*} [Fintype α]
    (G : SimpleGraph α) [DecidableRel G.Adj] (w : α → ℕ)
    (htri : G.CliqueFree 3) (hw : ∃ x, 0 < w x) :
    ∃ x, 0 < w x ∧ 2 * (∑ y ∈ G.neighborFinset x, w y) ≤ ∑ y, w y
Source
Weighted-neighborhood argument used in the Ramsey upper-bound proof, https://arxiv.org/abs/2401.00392, Proposition 2.1.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

The proof proceeds by contradiction: suppose every vertex with positive weight has a neighborhood whose weight strictly exceeds half of the total weight. Starting from an assumed positive-weight vertex x, its neighborhood must also have positive weight, so it contains an adjacent neighbor y with positive weight. Because the graph is triangle-free, the neighborhoods of the adjacent vertices x and y are disjoint, so the sum of their neighborhood weights cannot exceed the total graph weight. However, summing the contradiction hypotheses for x and y implies that the sum of their neighborhood weights strictly exceeds the total weight, reaching a contradiction.

  1. Assume for contradiction that every positive-weight vertex has neighborhood weight strictly exceeding half the total weight, and fix a positive-weight vertex x.

    We proceed by contradiction (`by_contra!`). Supposing the theorem is false, every vertex v with w(v) > 0 satisfies ∑ y, w y < 2 * ∑ y ∈ N(v), w y. The hypothesis hw supplies a vertex x with w(x) > 0, and specializing the contradiction assumption to x gives that the total weight is strictly less than twice the neighborhood weight of x.

    lines 5–8

      classical
      by_contra! h
      obtain ⟨x, hx⟩ := hw
      have hlarge : (∑ y, w y) < 2 * (∑ y ∈ G.neighborFinset x, w y) := h x hx
  2. The vertex x has an adjacent neighbor y with positive weight w(y) > 0.

    Since the total weight is a natural number strictly less than twice the neighborhood weight of x, that neighborhood weight must be strictly positive (`omega`). By `Finset.sum_pos_iff.mp`, a sum of nonnegative integers is positive only if at least one term is positive, yielding a neighbor y in N(x) with w(y) > 0. By `G.mem_neighborFinset`, membership in the neighborhood finset means x and y are adjacent in G.

    lines 9–11

    uses Finset.sum_pos_iff.mp, G.mem_neighborFinset

      have hpos : 0 < ∑ y ∈ G.neighborFinset x, w y := by omega
      obtain ⟨y, hy, hwy⟩ := Finset.sum_pos_iff.mp hpos
      have hxy : G.Adj x y := (G.mem_neighborFinset x y).mp hy
  3. The neighborhoods N(x) and N(y) are disjoint.

    To establish disjointness via `Finset.disjoint_left.mpr`, suppose toward a contradiction that some vertex z belongs to both N(x) and N(y). Then z is adjacent to both x and y (by `G.mem_neighborFinset`). In a triangle-free graph, the neighborhood of x is an independent set (`G.isIndepSet_neighborSet_of_triangleFree`). But y and z are distinct neighbors of x (distinct because they are adjacent, by `G.ne_of_adj`), so they cannot be adjacent, contradicting their adjacency.

    lines 12–17

    uses Finset.disjoint_left.mpr, G.mem_neighborFinset, G.isIndepSet_neighborSet_of_triangleFree, G.ne_of_adj

      have hdis : Disjoint (G.neighborFinset x) (G.neighborFinset y) := by
        apply Finset.disjoint_left.mpr
        intro z hzx hzy
        have hxz : G.Adj x z := (G.mem_neighborFinset x z).mp hzx
        have hyz : G.Adj y z := (G.mem_neighborFinset y z).mp hzy
        exact (G.isIndepSet_neighborSet_of_triangleFree htri x) hxy hxz (G.ne_of_adj hyz) hyz
  4. The sum of the neighborhood weights of x and y is at most the total weight of the graph.

    Because N(x) and N(y) are disjoint, the sum of their individual weights equals the sum over their union (`Finset.sum_union`). Since their union is a subset of the entire vertex set (`Finset.subset_univ`), its weight is bounded by the total sum of weights across all vertices (`Finset.sum_le_sum_of_subset`).

    lines 18–21

    uses Finset.sum_union, Finset.sum_le_sum_of_subset, Finset.subset_univ

      have hbound : (∑ z ∈ G.neighborFinset x, w z) +
          (∑ z ∈ G.neighborFinset y, w z) ≤ ∑ z, w z := by
        rw [← Finset.sum_union hdis]
        exact Finset.sum_le_sum_of_subset (Finset.subset_univ _)
  5. The contradiction hypotheses for x and y contradict the upper bound on their neighborhood weights.

    Since w(y) > 0, the contradiction assumption also applies to y, yielding that the total weight is strictly less than twice the neighborhood weight of y. Adding this to the corresponding inequality for x implies that twice the total weight is strictly less than twice the sum of the two neighborhood weights, contradicting the fact that the sum of the two neighborhood weights is at most the total weight. The linear arithmetic solver `omega` detects this contradiction and closes the proof.

    lines 22–23

      have hylarge : (∑ z, w z) < 2 * (∑ z ∈ G.neighborFinset y, w z) := h y hwy
      omega
Finset.sum_pos_iff.mp
A finite sum of nonnegative values is strictly positive only if some term in the sum is strictly positive.
G.mem_neighborFinset
A vertex belongs to the neighborhood finset of another vertex if and only if they are adjacent in the graph.
Finset.disjoint_left.mpr
Two finite sets are disjoint if no element of the first set belongs to the second set.
G.isIndepSet_neighborSet_of_triangleFree
In a triangle-free graph, the neighborhood of any vertex forms an independent set.
G.ne_of_adj
Two adjacent vertices in a simple graph are distinct.
Finset.sum_union
The sum of a function over the union of two disjoint finite sets is the sum of the sums over each set.
Finset.sum_le_sum_of_subset
The sum of nonnegative values over a subset is at most the sum over the superset.
Finset.subset_univ
Any finite set of elements of a finite type is a subset of the universal finset.

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

theorem simple_graph_triangle_free_weighted_low_neighborhood {α : Type*} [Fintype α]    (G : SimpleGraph α) [DecidableRel G.Adj] (w : α → ℕ)    (htri : G.CliqueFree 3) (hw : ∃ x, 0 < w x) :    ∃ x, 0 < w x ∧ 2 * (∑ y ∈ G.neighborFinset x, w y) ≤ ∑ y, w y := by  classical  by_contra! h  obtain ⟨x, hx⟩ := hw  have hlarge : (∑ y, w y) < 2 * (∑ y ∈ G.neighborFinset x, w y) := h x hx  have hpos : 0 < ∑ y ∈ G.neighborFinset x, w y := by omega  obtain ⟨y, hy, hwy⟩ := Finset.sum_pos_iff.mp hpos  have hxy : G.Adj x y := (G.mem_neighborFinset x y).mp hy  have hdis : Disjoint (G.neighborFinset x) (G.neighborFinset y) := by    apply Finset.disjoint_left.mpr    intro z hzx hzy    have hxz : G.Adj x z := (G.mem_neighborFinset x z).mp hzx    have hyz : G.Adj y z := (G.mem_neighborFinset y z).mp hzy    exact (G.isIndepSet_neighborSet_of_triangleFree htri x) hxy hxz (G.ne_of_adj hyz) hyz  have hbound : (∑ z ∈ G.neighborFinset x, w z) +      (∑ z ∈ G.neighborFinset y, w z) ≤ ∑ z, w z := by    rw [← Finset.sum_union hdis]    exact Finset.sum_le_sum_of_subset (Finset.subset_univ _)  have hylarge : (∑ z, w z) < 2 * (∑ z ∈ G.neighborFinset y, w z) := h y hwy  omega
See it in the graphDiscuss this resultChallenge it