AFTD Auto-Formalizing Theoretical Domains

additive_coloring_bipartite_maxDegree_add_one

theoremverifiedformalization

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.

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

    lines 8–9

    uses additive_coloring_bound_by_degree, Nat.one_pos

      obtain ⟨f, -, hf_adj, hf_bound⟩ :=
        additive_coloring_bound_by_degree G (fun _ => 1) (fun _ => Nat.one_pos)
  2. 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).

    line 10

      refine ⟨f, fun v => ⟨(hf_bound v).1, ?_⟩, hf_adj⟩
  3. 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.

    lines 11–13

    uses G.degree_le_maxDegree

      have := (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.

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

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