AFTD Auto-Formalizing Theoretical Domains

op_494_additive_chromatic_bipartite_maxDegree

theoremverifiedformalization

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

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.

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

    lines 10–11

    uses simple_graph_exists_edge_tail_capacity

      classical
      obtain ⟨tail, htail, hcap⟩ := simple_graph_exists_edge_tail_capacity G hdeg
  2. There 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$.

    lines 12–17

    uses simple_graph_bipartite_additive_lists_of_edge_assignment, Nat.card_Icc

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

    line 18

    uses Finset.mem_Icc.mp

      exact ⟨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$.

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