AFTD Auto-Formalizing Theoretical Domains

is_additive_coloring_le_iff

theoremverified

A vertex labeling f on a finite graph G is an additive coloring bounded by k if and only if 1 ≤ f(v) ≤ k for all vertices v and adjacent vertices have distinct neighborhood sums.

Statement

lemma is_additive_coloring_le_iff
    {V : Type*} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (f : V → ℕ) (k : ℕ) :
    (is_additive_coloring G f ∧ ∀ v, f v ≤ k) ↔
    (∀ v, 1 ≤ f v ∧ f v ≤ k) ∧
      (∀ ⦃u v : V⦄, G.Adj u v → ∑ w ∈ G.neighborFinset u, f w ≠ ∑ w ∈ G.neighborFinset v, f w)
Source
folklore
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • is_additive_coloringAn additive coloring of a finite simple graph G is a vertex labeling f : V → ℕ with positive integers such that for every edge {u, v}, the…

Read back from the Lean

For a finite type V, a simple graph G on V with decidable adjacency, a vertex labeling f : V → ℕ, and a natural number k: The conjunction that f is an additive coloring of G (is_additive_coloring G f) and that f v ≤ k for all v : V holds if and only if: 1. For all v : V, 1 ≤ f v ∧ f v ≤ k, and 2. For all vertices u, v : V such that u and v are adjacent in G (G.Adj u v), the sum of f w over all neighbors w of u (G.neighborFinset u) is not equal to the sum of f w over all neighbors w of v (G.neighborFinset v).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The equivalence is established by expanding the definition of an additive coloring into its two components: the positivity condition 0 < f(v) and the neighborhood sum inequality for adjacent vertices. Because 0 < f(v) and 1 ≤ f(v) are definitionally identical for natural numbers, the proof simply rearranges the logical conjunctions, pairing the lower bound 1 ≤ f(v) with the upper bound f(v) ≤ k pointwise for each vertex.

  1. The equivalence reduces to proving two implications after expanding the definition of an additive coloring.

    Unfolding `is_additive_coloring` expands the predicate into two conjuncts: that $f(v) > 0$ for all vertices $v$, and that adjacent vertices have distinct neighborhood sums. Splitting the bi-implication reduces the equivalence to showing each direction separately.

    lines 7–8

      unfold is_additive_coloring
      constructor
  2. If $f$ is an additive coloring bounded by $k$, then $1 \le f(v) \le k$ for all $v$ and adjacent vertices have distinct neighborhood sums.

    Assuming $f$ is an additive coloring bounded by $k$, we unpack the assumptions into strict positivity $0 < f(v)$ (which for natural numbers is $1 \le f(v)$), the neighborhood sum condition on adjacent vertices, and the upper bound $f(v) \le k$. For each vertex $v$, pairing $1 \le f(v)$ with $f(v) \le k$ yields $1 \le f(v) \le k$, while the neighborhood sum condition is retained as is.

    lines 9–10

      · rintro ⟨⟨hpos, hadj⟩, hle⟩
        exact ⟨fun v => ⟨hpos v, hle v⟩, hadj⟩
  3. Conversely, if $1 \le f(v) \le k$ for all $v$ and adjacent vertices have distinct neighborhood sums, then $f$ is an additive coloring bounded by $k$.

    Assuming $1 \le f(v) \le k$ for all $v$ and the neighborhood sum condition, we extract the lower bound $1 \le f(v)$ (definitionally $0 < f(v)$) and the upper bound $f(v) \le k$ for each vertex. Combining the lower bound with the neighborhood sum condition establishes `is_additive_coloring G f`, which along with the upper bound concludes the reverse direction.

    lines 11–12

      · rintro ⟨h1, hadj⟩
        exact ⟨⟨fun v => (h1 v).1, hadj⟩, fun v => (h1 v).2⟩

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

/-- Equivalence between the is_additive_coloring predicate with an upper bound and the explicit bounded neighborhood sum condition. -/lemma is_additive_coloring_le_iff    {V : Type*} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (f : V → ℕ) (k : ℕ) :    (is_additive_coloring G f ∧ ∀ v, f v ≤ k) ↔    (∀ v, 1 ≤ f v ∧ f v ≤ k) ∧      (∀ ⦃u v : V⦄, G.Adj u v → ∑ w ∈ G.neighborFinset u, f w ≠ ∑ w ∈ G.neighborFinset v, f w) := by  unfold is_additive_coloring  constructor  · rintro ⟨⟨hpos, hadj⟩, hle⟩    exact ⟨fun v => ⟨hpos v, hle v⟩, hadj⟩  · rintro ⟨h1, hadj⟩    exact ⟨⟨fun v => (h1 v).1, hadj⟩, fun v => (h1 v).2⟩
See it in the graphDiscuss this resultChallenge it