additive_coloring_bipartite_maxDegree_add_one
Every finite connected bipartite graph with maximum degree at least 2 admits an additive coloring f with 1 ≤ f(v) ≤ Delta(G) + 1 for all vertices v.
Statement
theorem additive_coloring_bipartite_maxDegree_add_one {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (_hconn : G.Connected) (_hbip : G.IsBipartite) (_hdeg : 2 ≤ G.maxDegree) : ∃ f : V → ℕ, (∀ v, 1 ≤ f v ∧ f v ≤ G.maxDegree + 1) ∧ ∀ ⦃u v : V⦄, G.Adj u v → ∑ w ∈ G.neighborFinset u, f w ≠ ∑ w ∈ G.neighborFinset v, f w
- Formalizes
- arXiv:2610.30174: Theorem 2.1
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- additive_coloring_bound_by_degreeLet G = (V, E) be a finite simple graph, and let a : V → ℕ assign a positive integer to each vertex. Then there exists an additive…
Read back from the Lean
Let V be a finite type with decidable equality, and let G be a simple graph on V with decidable adjacency. Suppose G is connected, G is bipartite, and the maximum degree of G is at least 2. Then there exists a function f : V → ℕ such that: 1. For every vertex v ∈ V, 1 ≤ f v ≤ G.maxDegree + 1; and 2. For all vertices u, v ∈ V, if u is adjacent to v in G, then the sum of f w over all neighbors w of u is not equal to the sum of f w over all neighbors w of v (i.e., ∑ w ∈ G.neighborFinset u, f w ≠ ∑ w ∈ G.neighborFinset v, f w).
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 proof applies a general theorem, `additive_coloring_bound_by_degree`, which guarantees the existence of an additive coloring bounded by a(v) ≤ f(v) ≤ a(v) + deg(v) for any strictly positive function a. Setting a(v) = 1 everywhere gives 1 ≤ f(v) ≤ 1 + deg(v). Since the degree of every vertex is at most the maximum degree Δ(G), the upper bound f(v) ≤ Δ(G) + 1 follows immediately.
There exists an additive coloring f : V → ℕ such that 1 ≤ f(v) ≤ 1 + deg(v) for every vertex v.
We apply `additive_coloring_bound_by_degree` with the constant lower bound a(v) = 1, which is strictly positive everywhere by `Nat.one_pos`. This yields a coloring f whose neighbor sums differ on adjacent vertices (`hf_adj`) and which satisfies 1 ≤ f(v) ≤ 1 + deg(v) for every vertex v (`hf_bound`).
uses
additive_coloring_bound_by_degree,Nat.one_posobtain ⟨f, -, hf_adj, hf_bound⟩ := additive_coloring_bound_by_degree G (fun _ => 1) (fun _ => Nat.one_pos)
Supplying f reduces the goal to proving that f(v) ≤ Δ(G) + 1 for each vertex v.
The witness f already distinguishes adjacent vertices by neighbor sums, and the lower bound 1 ≤ f(v) is given directly by the first component of `hf_bound v`. It remains only to establish the upper bound on f(v).
refine ⟨f, fun v => ⟨(hf_bound v).1, ?_⟩, hf_adj⟩
For any vertex v, f(v) ≤ Δ(G) + 1.
The second component of `hf_bound v` gives f(v) ≤ 1 + deg(v). Since deg(v) ≤ Δ(G) by `G.degree_le_maxDegree`, linear integer arithmetic (`omega`) finishes the inequality.
uses
G.degree_le_maxDegreehave := (hf_bound v).2 have hdeg_le : G.degree v ≤ G.maxDegree := G.degree_le_maxDegree v omega
additive_coloring_bound_by_degree- For any finite graph G and any strictly positive function a : V → ℕ, there exists an additive coloring f : V → ℕ such that a(v) ≤ f(v) ≤ a(v) + deg(v) for all vertices v.
Nat.one_pos- Zero is strictly less than one (0 < 1).
G.degree_le_maxDegree- The degree of any vertex v in a finite graph G is at most the maximum degree Δ(G) of the graph.
- The hypotheses that G is connected (_hconn), bipartite (_hbip), and has maximum degree at least 2 (_hdeg) are completely unused in the proof; the result holds for all finite graphs.
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.
/-- Every finite connected bipartite graph with maximum degree at least 2 admits an additive coloring with labels at most its maximum degree plus 1. -/theorem additive_coloring_bipartite_maxDegree_add_one {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (_hconn : G.Connected) (_hbip : G.IsBipartite) (_hdeg : 2 ≤ G.maxDegree) : ∃ f : V → ℕ, (∀ v, 1 ≤ f v ∧ f v ≤ G.maxDegree + 1) ∧ ∀ ⦃u v : V⦄, G.Adj u v → ∑ w ∈ G.neighborFinset u, f w ≠ ∑ w ∈ G.neighborFinset v, f w := by obtain ⟨f, -, hf_adj, hf_bound⟩ := additive_coloring_bound_by_degree G (fun _ => 1) (fun _ => Nat.one_pos) refine ⟨f, fun v => ⟨(hf_bound v).1, ?_⟩, hf_adj⟩ have := (hf_bound v).2 have hdeg_le : G.degree v ≤ G.maxDegree := G.degree_le_maxDegree v omega