is_additive_coloring_le_iff
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.
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.
unfold is_additive_coloring constructor
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.
· rintro ⟨⟨hpos, hadj⟩, hle⟩ exact ⟨fun v => ⟨hpos v, hle v⟩, hadj⟩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.
· rintro ⟨h1, hadj⟩ exact ⟨⟨fun v => (h1 v).1, hadj⟩, fun v => (h1 v).2⟩
- In Lean 4, `0 < n` and `1 ≤ n` for a natural number `n : ℕ` are definitionally equal (both reduce to `Nat.le 1 n`). As a result, the proof interchanges `0 < f v` and `1 ≤ f v` without needing any conversion lemma.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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⟩