simple_graph_bipartite_additive_lists_of_edge_assignment
A finite bipartite graph admits an additive coloring from arbitrary finite natural label lists when each list size exceeds the number of edges assigned to that endpoint.
Statement
theorem simple_graph_bipartite_additive_lists_of_edge_assignment {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hbip : G.IsBipartite) (tail : G.edgeSet → V) (htail : ∀ e : G.edgeSet, tail e ∈ (e : Sym2 V)) (L : V → Finset ℕ) (hL : ∀ v, (Finset.univ.filter (fun e => tail e = v)).card < (L v).card) : ∃ f : V → ℕ, (∀ v, f v ∈ L v) ∧ ∀ ⦃u v : V⦄, G.Adj u v → ∑ w ∈ G.neighborFinset u, f w ≠ ∑ w ∈ G.neighborFinset v, f w
- Source
- Helper for OP-494 in arXiv:2610.30174, following the additive-list coloring argument of arXiv:2302.02190v3, Corollary 5.3. Take the union of the two neighbor sets for each edge, negate the lists on one bipartition class, and recover distinct natural neighborhood sums from the nonzero signed evaluations.
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- exists_signed_nonzero_linear_formsA family of sums of variables admits a simultaneous nonzero evaluation on finite integer lists whose sizes exceed the selection…
- Used by 1
- op_494_additive_chromatic_bipartite_maxDegreeLet G be a finite connected bipartite simple graph with maximum degree at least 2. Then there exists a vertex labeling f : V → ℕ such that…
The proof, explained
Using the bipartite assumption, the graph G is equipped with a proper 2-coloring c : V → {0, 1}. For each edge e = uv, we define A(e) = N(u) ∪ N(v) and construct signed integer lists L'(v) by negating the elements of L(v) when c(v) = 0. Applying the Combinatorial Nullstellensatz-style theorem `exists_signed_nonzero_linear_forms`, we obtain a signed choice x(v) ∈ L'(v) whose sum over each A(e) is nonzero. Because G is bipartite, the neighborhoods N(u) and N(v) are disjoint and each is monochromatic of the opposite color, which forces the sum of x over A(uv) to equal ±(∑_{w ∈ N(u)} f(w) - ∑_{w ∈ N(v)} f(w)) ≠ 0. This shows that the extracted label selection f(v) ∈ L(v) satisfies the additive coloring condition on all edges.
Extract a 2-coloring `c : V → {0, 1}` of `G` and define `A(e) = N(u) ∪ N(v)` for each edge `e = uv`.
Using classical reasoning, the bipartite hypothesis gives a proper 2-coloring `c : V → Fin 2`. For each edge `e`, we define `A(e)` to be the union of the neighbor sets of its two endpoints.
classical obtain ⟨c⟩ := hbip let A : G.edgeSet → Finset V := fun e => (e : Sym2 V).toFinset.biUnion (fun v => G.neighborFinset v)
For every edge `e`, its assigned tail vertex `tail(e)` belongs to `A(e)`.
Any edge `e` connects two vertices `u` and `v`. The tail `tail(e)` must be either `u` or `v`. If `tail(e) = u`, then since `u` is adjacent to `v`, `u ∈ N(v) ⊆ A(e)`. Symmetrically, if `tail(e) = v`, then `v ∈ N(u) ⊆ A(e)`. In both cases, `tail(e) ∈ A(e)`.
uses
Sym2.mem_iff,Finset.mem_biUnion.mprhave htailA : ∀ e, tail e ∈ A e := by rintro ⟨⟨u, v⟩, huv⟩ have h := htail ⟨s(u, v), huv⟩ simp only [Sym2.mem_iff] at h change tail ⟨s(u, v), huv⟩ ∈ (s(u, v).toFinset.biUnion (fun v => G.neighborFinset v)) rcases h with h | h · apply Finset.mem_biUnion.mpr refine ⟨v, by simp, ?_⟩ rw [h, G.mem_neighborFinset] exact (G.mem_edgeSet.mp huv).symm · apply Finset.mem_biUnion.mpr refine ⟨u, by simp, ?_⟩ rw [h, G.mem_neighborFinset] exact G.mem_edgeSet.mp huv
Define signed integer lists `L'(v)` by negating elements of `L(v)` when `c(v) = 0`, preserving set sizes.
For each vertex `v`, we define `L'(v)` as the image of `L(v)` under `a ↦ -a` if `c(v) = 0`, and `a ↦ a` otherwise. This map is injective, so `|L'(v)| = |L(v)|`. Hence the hypothesis that the list size strictly exceeds the number of edges oriented towards `v` still holds for `L'`.
uses
if_pos,neg_inj,Int.ofNat_inj.mp,if_neg,Finset.card_image_of_injectivelet L' : V → Finset ℤ := fun v => (L v).image (fun a : ℕ => if c v = 0 then -(a : ℤ) else (a : ℤ)) have hL' : ∀ v, (Finset.univ.filter (fun e => tail e = v)).card < (L' v).card := by intro v have hinj : Function.Injective (fun a : ℕ => if c v = 0 then -(a : ℤ) else (a : ℤ)) := by intro a b hab by_cases hc : c v = 0 · simp only [if_pos hc, neg_inj] at hab exact Int.ofNat_inj.mp hab · simp only [if_neg hc] at hab exact Int.ofNat_inj.mp hab simpa only [L', Finset.card_image_of_injective _ hinj] using hL v
Select `f(v) ∈ L(v)` from an integer assignment `x(v) ∈ L'(v)` whose linear forms over each `A(e)` are nonzero.
Applying `exists_signed_nonzero_linear_forms` to `A`, `tail`, and `L'` produces an assignment `x : V → ℤ` with `x(v) ∈ L'(v)` such that `∑_{w ∈ A(e)} x(w) ≠ 0` for all edges `e`. Since each `x(v)` comes from some label in `L(v)`, the axiom of choice yields a function `f : V → ℕ` with `f(v) ∈ L(v)` and `x(v) = -f(v)` if `c(v) = 0`, `x(v) = f(v)` if `c(v) ≠ 0`.
uses
exists_signed_nonzero_linear_forms,Finset.mem_image.mpobtain ⟨x, hx, hxne⟩ := exists_signed_nonzero_linear_forms A tail htailA L' hL' have hx' : ∀ v, ∃ a ∈ L v, x v = if c v = 0 then -(a : ℤ) else (a : ℤ) := by intro v obtain ⟨a, ha, hax⟩ := Finset.mem_image.mp (hx v) exact ⟨a, ha, hax.symm⟩ choose f hf hxf using hx'
Any two neighbors `v` and `w` of a vertex `u` have the same color under `c`.
Because `c` is a proper 2-coloring, both `c(v)` and `c(w)` must differ from `c(u)`. Since the color set `Fin 2` has only two elements, `c(v)` and `c(w)` must be equal.
uses
Fin.exthave hcolors {u v w : V} (huv : G.Adj u v) (huw : G.Adj u w) : c v = c w := by have hv := c.valid huv have hw := c.valid huw apply Fin.ext have hu' := (c u).isLt have hv' := (c v).isLt have hw' := (c w).isLt omega
For any edge `uv`, the sum of `x(w)` over `w ∈ N(u)` equals `-∑_{w ∈ N(u)} f(w)` if `c(v) = 0`, and `∑_{w ∈ N(u)} f(w)` otherwise.
Every neighbor `w ∈ N(u)` satisfies `c(w) = c(v)`. When `c(v) = 0`, every `x(w) = -f(w)`, so the sum equals `-∑ f(w)`. When `c(v) ≠ 0`, every `x(w) = f(w)`, so the sum equals `∑ f(w)`.
uses
Finset.sum_neg_distrib,Finset.sum_congrhave hsum {u v : V} (huv : G.Adj u v) : (∑ w ∈ G.neighborFinset u, x w) = if c v = 0 then -(∑ w ∈ G.neighborFinset u, (f w : ℤ)) else ∑ w ∈ G.neighborFinset u, (f w : ℤ) := by split_ifs with hv0 · rw [← Finset.sum_neg_distrib] apply Finset.sum_congr rfl intro w hw rw [hxf, ← hcolors huv ((G.mem_neighborFinset u w).mp hw)] simp [hv0] · apply Finset.sum_congr rfl intro w hw rw [hxf, ← hcolors huv ((G.mem_neighborFinset u w).mp hw)] simp [hv0]
To verify `f` is an additive coloring, assume for contradiction that an edge `uv` has equal neighbor sums; then `N(u)` and `N(v)` are disjoint.
We supply `f` as the coloring. Suppose for contradiction that `∑_{w ∈ N(u)} f(w) = ∑_{w ∈ N(v)} f(w)` for an edge `uv`. A common neighbor `w` would satisfy `c(u) = c(w) = c(v)`, contradicting that `c` properly colors the edge `uv`. Thus `N(u)` and `N(v)` are disjoint.
uses
Finset.disjoint_left.mprrefine ⟨f, hf, ?_⟩ intro u v huv heq have hdisj : Disjoint (G.neighborFinset u) (G.neighborFinset v) := by apply Finset.disjoint_left.mpr intro w hwu hwv have heq := hcolors ((G.mem_neighborFinset u w).mp hwu).symm ((G.mem_neighborFinset v w).mp hwv).symm exact c.valid huv heq
The sum of `x` over `A(uv)` splits into the sums over `N(u)` and `N(v)`, which is nonzero, while the integer neighbor sums of `f` are equal.
Since `A(uv) = N(u) ∪ N(v)` is a disjoint union, the sum `∑_{w ∈ A(uv)} x(w)` equals `∑_{w ∈ N(u)} x(w) + ∑_{w ∈ N(v)} x(w)`, which is nonzero by the choice of `x`. Meanwhile, the assumed equality of neighbor sums of `f` carries over to integers.
uses
Sym2.toFinset_mk_eq,Finset.biUnion_insert,Finset.singleton_biUnion,Finset.sum_unionhave hne := hxne ⟨s(u, v), G.mem_edgeSet.mpr huv⟩ change (∑ w ∈ s(u, v).toFinset.biUnion (fun v => G.neighborFinset v), x w) ≠ 0 at hne simp only [Sym2.toFinset_mk_eq, Finset.biUnion_insert, Finset.singleton_biUnion] at hne rw [Finset.sum_union hdisj, hsum huv, hsum huv.symm] at hne have hs : (∑ w ∈ G.neighborFinset u, (f w : ℤ)) = ∑ w ∈ G.neighborFinset v, (f w : ℤ) := by exact_mod_cast heq
Evaluating the sum of `x` over `A(uv)` produces `0 ≠ 0` in both cases `c(u) = 0` and `c(u) ≠ 0`, completing the contradiction.
Since `uv` is an edge, exactly one of `u, v` has color `0` and the other has color `1`. If `c(u) = 0`, then `c(v) ≠ 0`, so the sum over `A(uv)` is `∑_{w ∈ N(u)} f(w) - ∑_{w ∈ N(v)} f(w) = 0`, contradicting nonzeroness. If `c(u) ≠ 0`, then `c(v) = 0`, giving `-∑_{w ∈ N(u)} f(w) + ∑_{w ∈ N(v)} f(w) = 0`, which is likewise impossible. Thus adjacent vertices cannot have equal neighbor sums.
uses
Fin.extby_cases hu0 : c u = 0 · have hv0 : c v ≠ 0 := fun hv0 => c.valid huv (hu0.trans hv0.symm) simp [hu0, hv0, hs] at hne · have hv0 : c v = 0 := by have hneq := c.valid huv apply Fin.ext have hu' := (c u).isLt have hv' := (c v).isLt omega simp [hu0, hv0, hs] at hne
Sym2.mem_iff- An element belongs to an unordered pair `s(b, c)` if and only if it equals `b` or `c`.
Finset.mem_biUnion.mpr- If there exists `a ∈ s` such that `b ∈ t(a)`, then `b` belongs to the indexed union of `t` over `s`.
if_pos- An if-then-else expression evaluates to the then-branch when the condition holds.
neg_inj- Negation is injective: `-a = -b` if and only if `a = b`.
Int.ofNat_inj.mp- If the integer coercions of two natural numbers are equal, then the natural numbers are equal.
if_neg- An if-then-else expression evaluates to the else-branch when the condition is false.
Finset.card_image_of_injective- The image of a finite set under an injective function has the same cardinality as the original set.
exists_signed_nonzero_linear_forms- For an edge-indexed family of finite sets `A(e)`, a choice of vertex `f(e) ∈ A(e)` for each edge, and integer lists `L(v)` whose sizes exceed the assigned tail degrees, there exists a selection `x(v) ∈ L(v)` such that the sum of `x` over `A(e)` is nonzero for every edge `e`.
Finset.mem_image.mp- If an element is in the image of a set under a function, it is the image of some element in that set.
Fin.ext- Two elements of `Fin n` are equal if and only if their underlying natural numbers are equal.
Finset.sum_neg_distrib- The sum of the negations of elements is the negation of their sum.
Finset.sum_congr- Two finite sums are equal if their index sets are equal and their summands agree on every element of the index set.
Finset.disjoint_left.mpr- Two finite sets are disjoint if no element in the first set belongs to the second set.
Sym2.toFinset_mk_eq- The finite set representation of an unordered pair `s(x, y)` is the two-element set `{x, y}`.
Finset.biUnion_insert- The indexed union over `insert a s` equals the set at `a` unioned with the indexed union over `s`.
Finset.singleton_biUnion- The indexed union over a singleton set `{a}` is the set at `a`.
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.
- The proof relies on `exists_signed_nonzero_linear_forms`, an external lemma in this knowledge base that establishes the existence of non-vanishing signed linear combinations over integer lists using Combinatorial Nullstellensatz-style methods.
- The `omega` tactic is invoked to verify the pigeonhole principle on `Fin 2 = {0, 1}`: since neighbors in a proper 2-coloring must have different colors from the center vertex, any two neighbors must share the same color.
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 BigOperatorstheorem simple_graph_bipartite_additive_lists_of_edge_assignment {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hbip : G.IsBipartite) (tail : G.edgeSet → V) (htail : ∀ e : G.edgeSet, tail e ∈ (e : Sym2 V)) (L : V → Finset ℕ) (hL : ∀ v, (Finset.univ.filter (fun e => tail e = v)).card < (L v).card) : ∃ f : V → ℕ, (∀ v, f v ∈ L v) ∧ ∀ ⦃u v : V⦄, G.Adj u v → ∑ w ∈ G.neighborFinset u, f w ≠ ∑ w ∈ G.neighborFinset v, f w := by classical obtain ⟨c⟩ := hbip let A : G.edgeSet → Finset V := fun e => (e : Sym2 V).toFinset.biUnion (fun v => G.neighborFinset v) have htailA : ∀ e, tail e ∈ A e := by rintro ⟨⟨u, v⟩, huv⟩ have h := htail ⟨s(u, v), huv⟩ simp only [Sym2.mem_iff] at h change tail ⟨s(u, v), huv⟩ ∈ (s(u, v).toFinset.biUnion (fun v => G.neighborFinset v)) rcases h with h | h · apply Finset.mem_biUnion.mpr refine ⟨v, by simp, ?_⟩ rw [h, G.mem_neighborFinset] exact (G.mem_edgeSet.mp huv).symm · apply Finset.mem_biUnion.mpr refine ⟨u, by simp, ?_⟩ rw [h, G.mem_neighborFinset] exact G.mem_edgeSet.mp huv let L' : V → Finset ℤ := fun v => (L v).image (fun a : ℕ => if c v = 0 then -(a : ℤ) else (a : ℤ)) have hL' : ∀ v, (Finset.univ.filter (fun e => tail e = v)).card < (L' v).card := by intro v have hinj : Function.Injective (fun a : ℕ => if c v = 0 then -(a : ℤ) else (a : ℤ)) := by intro a b hab by_cases hc : c v = 0 · simp only [if_pos hc, neg_inj] at hab exact Int.ofNat_inj.mp hab · simp only [if_neg hc] at hab exact Int.ofNat_inj.mp hab simpa only [L', Finset.card_image_of_injective _ hinj] using hL v obtain ⟨x, hx, hxne⟩ := exists_signed_nonzero_linear_forms A tail htailA L' hL' have hx' : ∀ v, ∃ a ∈ L v, x v = if c v = 0 then -(a : ℤ) else (a : ℤ) := by intro v obtain ⟨a, ha, hax⟩ := Finset.mem_image.mp (hx v) exact ⟨a, ha, hax.symm⟩ choose f hf hxf using hx' have hcolors {u v w : V} (huv : G.Adj u v) (huw : G.Adj u w) : c v = c w := by have hv := c.valid huv have hw := c.valid huw apply Fin.ext have hu' := (c u).isLt have hv' := (c v).isLt have hw' := (c w).isLt omega have hsum {u v : V} (huv : G.Adj u v) : (∑ w ∈ G.neighborFinset u, x w) = if c v = 0 then -(∑ w ∈ G.neighborFinset u, (f w : ℤ)) else ∑ w ∈ G.neighborFinset u, (f w : ℤ) := by split_ifs with hv0 · rw [← Finset.sum_neg_distrib] apply Finset.sum_congr rfl intro w hw rw [hxf, ← hcolors huv ((G.mem_neighborFinset u w).mp hw)] simp [hv0] · apply Finset.sum_congr rfl intro w hw rw [hxf, ← hcolors huv ((G.mem_neighborFinset u w).mp hw)] simp [hv0] refine ⟨f, hf, ?_⟩ intro u v huv heq have hdisj : Disjoint (G.neighborFinset u) (G.neighborFinset v) := by apply Finset.disjoint_left.mpr intro w hwu hwv have heq := hcolors ((G.mem_neighborFinset u w).mp hwu).symm ((G.mem_neighborFinset v w).mp hwv).symm exact c.valid huv heq have hne := hxne ⟨s(u, v), G.mem_edgeSet.mpr huv⟩ change (∑ w ∈ s(u, v).toFinset.biUnion (fun v => G.neighborFinset v), x w) ≠ 0 at hne simp only [Sym2.toFinset_mk_eq, Finset.biUnion_insert, Finset.singleton_biUnion] at hne rw [Finset.sum_union hdisj, hsum huv, hsum huv.symm] at hne have hs : (∑ w ∈ G.neighborFinset u, (f w : ℤ)) = ∑ w ∈ G.neighborFinset v, (f w : ℤ) := by exact_mod_cast heq by_cases hu0 : c u = 0 · have hv0 : c v ≠ 0 := fun hv0 => c.valid huv (hu0.trans hv0.symm) simp [hu0, hv0, hs] at hne · have hv0 : c v = 0 := by have hneq := c.valid huv apply Fin.ext have hu' := (c u).isLt have hv' := (c v).isLt omega simp [hu0, hv0, hs] at hne