op_494_additive_chromatic_bipartite_maxDegree
Let G be a finite connected bipartite simple graph with maximum degree at least 2. Then there exists a vertex labeling f : V → ℕ such that 1 ≤ f(v) ≤ G.maxDegree for all v, and adjacent vertices have different neighborhood sums ∑_{w ∈ N(u)} f(w) ≠ ∑_{w ∈ N(v)} f(w).
Statement
theorem op_494_additive_chromatic_bipartite_maxDegree {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) ∧ ∀ ⦃u v : V⦄, G.Adj u v → ∑ w ∈ G.neighborFinset u, f w ≠ ∑ w ∈ G.neighborFinset v, f w
- Formalizes
- Known consequence of arXiv:2302.02190v3, Corollary 5.3, and the standard incidence matching construction of an orientation with outdegree at most maximum-degree-minus-one when the maximum degree is at least two. Formalizes OP-494 in arXiv:2610.30174; this is a literature consequence, not a new research result.
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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…
- simple_graph_exists_edge_tail_capacityEvery finite simple graph of maximum degree at least two admits an assignment of each edge to one of its endpoints, with at most…
- simple_graph_bipartite_additive_lists_of_edge_assignmentA finite bipartite graph admits an additive coloring from arbitrary finite natural label lists when each list size exceeds the number of…
Read back from the Lean
For every finite type $V$ with decidable equality and every simple graph $G$ on $V$ with decidable adjacency, if $G$ is connected, $G$ is bipartite, and the maximum degree of $G$ is at least 2, then there exists a labeling $f : V \to \mathbb{N}$ such that: 1. For every vertex $v \in V$, $1 \le f(v) \le G.\mathrm{maxDegree}$. 2. For all vertices $u, v \in V$, if $u$ and $v$ are adjacent 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., $\sum_{w \in G.\mathrm{neighborFinset}\; u} f(w) \ne \sum_{w \in G.\mathrm{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 solves the additive coloring problem for bipartite graphs by combining an edge orientation with a list-coloring result based on the Combinatorial Nullstellensatz. First, `simple_graph_exists_edge_tail_capacity` provides an edge-tail orientation in which every vertex is assigned at most $\Delta(G) - 1$ edges. Second, `simple_graph_bipartite_additive_lists_of_edge_assignment` guarantees an additive coloring whenever each vertex's color list strictly exceeds its out-degree in the orientation. Setting each vertex's list to $\{1, \dots, \Delta(G)\}$ provides $\Delta(G) > \Delta(G) - 1$ colors, satisfying the hypothesis and yielding the required labeling.
There exists an orientation assigning each edge to one of its endpoints such that every vertex is the tail of at most $\Delta(G) - 1$ edges.
Enabling classical logic, we apply `simple_graph_exists_edge_tail_capacity` using the assumption $2 \le G.\text{maxDegree}$ (`hdeg`). This produces an orientation function `tail` mapping each edge to one of its endpoints (`htail`) such that each vertex $v$ serves as the tail of at most $G.\text{maxDegree} - 1$ edges (`hcap`).
uses
simple_graph_exists_edge_tail_capacityclassical obtain ⟨tail, htail, hcap⟩ := simple_graph_exists_edge_tail_capacity G hdegThere exists a vertex labeling $f : V \to \mathbb{N}$ choosing colors from $\{1, \dots, \Delta(G)\}$ such that adjacent vertices have different neighborhood sums.
We apply `simple_graph_bipartite_additive_lists_of_edge_assignment` to the bipartite graph $G$ with the edge orientation `tail` and uniform color list $L(v) = \{1, \dots, G.\text{maxDegree}\}$. In lines 14–17, we establish the list-size hypothesis: the number of edges oriented from $v$ is at most $G.\text{maxDegree} - 1$ by `hcap`, while the size of the list is $|L(v)| = G.\text{maxDegree} + 1 - 1$ by `Nat.card_Icc`. Linear integer arithmetic (`omega`) closes the strict inequality $|\{e \mid \text{tail}(e) = v\}| < |L(v)|$, yielding the desired labeling $f$.
uses
simple_graph_bipartite_additive_lists_of_edge_assignment,Nat.card_Iccobtain ⟨f, hf, hadd⟩ := simple_graph_bipartite_additive_lists_of_edge_assignment G hbip tail htail (fun _ => Finset.Icc 1 G.maxDegree) (by intro v have hc := hcap v simp only [Nat.card_Icc] omega)
The function $f$ satisfies $1 \le f(v) \le \Delta(G)$ for all $v$ and has different neighborhood sums on adjacent vertices.
We provide $f$ as the existential witness. The condition $f(v) \in \{1, \dots, G.\text{maxDegree}\}$ is unpacked into $1 \le f(v) \wedge f(v) \le G.\text{maxDegree}$ using `Finset.mem_Icc.mp`, while the distinct neighborhood sum property is given directly by `hadd`.
uses
Finset.mem_Icc.mpexact ⟨f, fun v => Finset.mem_Icc.mp (hf v), hadd⟩
simple_graph_exists_edge_tail_capacity- In any finite graph with maximum degree at least 2, there exists an assignment of each edge to one of its endpoints such that every vertex is chosen at most $\Delta(G) - 1$ times.
simple_graph_bipartite_additive_lists_of_edge_assignment- In a bipartite graph with an edge-tail orientation and candidate color lists $L(v)$ at each vertex, if every vertex is the tail of strictly fewer edges than the size of its list, there exists a labeling $f(v) \in L(v)$ such that adjacent vertices have different neighborhood sums.
Nat.card_Icc- The cardinality of the closed interval of natural numbers $[a, b]$ is $b + 1 - a$.
Finset.mem_Icc.mp- If an element $x$ belongs to the closed interval $[a, b]$, then $a \le x$ and $x \le b$.
- The theorem statement includes the hypothesis that $G$ is connected (`hconn`), but this hypothesis is unused in the proof; the result holds for all finite bipartite graphs with maximum degree at least 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
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.
open scoped BigOperators/-- Open Problem OP-494: every connected bipartite finite simple graph with maximum degree at least 2 admits an additive coloring with labels at most its maximum degree. -/theorem op_494_additive_chromatic_bipartite_maxDegree {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) ∧ ∀ ⦃u v : V⦄, G.Adj u v → ∑ w ∈ G.neighborFinset u, f w ≠ ∑ w ∈ G.neighborFinset v, f w := by classical obtain ⟨tail, htail, hcap⟩ := simple_graph_exists_edge_tail_capacity G hdeg obtain ⟨f, hf, hadd⟩ := simple_graph_bipartite_additive_lists_of_edge_assignment G hbip tail htail (fun _ => Finset.Icc 1 G.maxDegree) (by intro v have hc := hcap v simp only [Nat.card_Icc] omega) exact ⟨f, fun v => Finset.mem_Icc.mp (hf v), hadd⟩