AFTD Auto-Formalizing Theoretical Domains

simple_graph_bipartite_additive_lists_of_edge_assignment

theoremverified

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
Used by 1

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.

  1. 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.

    lines 12–15

      classical
      obtain ⟨c⟩ := hbip
      let A : G.edgeSet → Finset V := fun e =>
        (e : Sym2 V).toFinset.biUnion (fun v => G.neighborFinset v)
  2. 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)`.

    lines 16–30

    uses Sym2.mem_iff, Finset.mem_biUnion.mpr

      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
  3. 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'`.

    lines 31–42

    uses if_pos, neg_inj, Int.ofNat_inj.mp, if_neg, Finset.card_image_of_injective

      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
  4. 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`.

    lines 43–48

    uses exists_signed_nonzero_linear_forms, Finset.mem_image.mp

      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'
  5. 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.

    lines 49–56

    uses Fin.ext

      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
  6. 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)`.

    lines 57–70

    uses Finset.sum_neg_distrib, Finset.sum_congr

      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]
  7. 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.

    lines 71–78

    uses Finset.disjoint_left.mpr

      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
  8. 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.

    lines 79–85

    uses Sym2.toFinset_mk_eq, Finset.biUnion_insert, Finset.singleton_biUnion, Finset.sum_union

      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
  9. 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.

    lines 86–95

    uses Fin.ext

      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
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.

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

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
See it in the graphDiscuss this resultChallenge it