AFTD Auto-Formalizing Theoretical Domains

simple_graph_achromatic_number_le_max_degree_or_half

theoremverifiedformalization

For every finite graph, χ_a(G) ≤ max{Δ(G) + 1, ⌊n/2⌋}: if some colour class is a single vertex, that vertex has a neighbour in each of the other classes; otherwise every class has at least two vertices.

Statement

theorem simple_graph_achromatic_number_le_max_degree_or_half {V : Type*} [Fintype V]
    [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] :
    simple_graph_achromatic_number G ≤ max (G.maxDegree + 1) (Fintype.card V / 2)
Formalizes
arXiv:2610.27510 (The achromatic number of Paley graphs, Peisert graphs, and related Cayley graphs), Proposition 3.1 (stated there for the pseudochromatic number, which is at least χ_a; the Lean is the achromatic case)
Verified
21 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
Used by 3

The proof, explained

To bound the achromatic number χ_a(G), it suffices to show that any achromatic coloring C using k colors satisfies k ≤ max{Δ(G) + 1, ⌊|V|/2⌋}. The argument splits on whether some color class has at most one vertex. If some color class consists of a single vertex v, then the achromatic condition forces v to have a neighbor in every other color class, giving k - 1 ≤ deg(v) ≤ Δ(G) and thus k ≤ Δ(G) + 1. Otherwise, every color class has at least two vertices, so summing the class sizes gives 2k ≤ |V|, whence k ≤ ⌊|V|/2⌋.

  1. To bound the achromatic number, it suffices to show that any achromatic coloring using k colors satisfies k ≤ max{Δ(G) + 1, ⌊|V|/2⌋}.

    By definition, the achromatic number χ_a(G) is the supremum of the number of colors k among all achromatic colorings of G. By `csSup_le'`, this supremum is bounded by max{Δ(G) + 1, ⌊|V|/2⌋} provided that value is an upper bound on every such k. We therefore consider an arbitrary k and an achromatic coloring C with k colors.

    lines 4–6

    uses csSup_le'

      dsimp [simple_graph_achromatic_number]
      apply csSup_le'
      rintro k ⟨C, hC⟩
  2. The argument splits into two cases: either some color class has size at most 1, or every color class has size at least 2.

    We perform a case split on whether there exists a color i ∈ Fin k whose fiber C⁻¹(i) has cardinality at most 1.

    line 7

      by_cases h : ∃ i : Fin k, (Finset.univ.filter (fun a => C a = i)).card ≤ 1
  3. In the first case, there is a color i whose color class consists of a unique vertex v.

    Let i be a color whose fiber has size at most 1. By surjectivity of the achromatic coloring C (`hC.1`), there is at least one vertex v of color i. Since the fiber has at most one element, any vertex u with C(u) = i must be equal to v by `Finset.card_le_one_iff.mp`.

    lines 8–18

    uses Finset.mem_filter, Finset.mem_univ, Finset.card_le_one_iff.mp

      · obtain ⟨i, hi⟩ := h
        obtain ⟨v, hv⟩ := hC.1 i
        have hv_mem : v ∈ Finset.univ.filter (fun a => C a = i) := by
          rw [Finset.mem_filter]
          exact ⟨Finset.mem_univ v, hv⟩
        have h_unique : ∀ u, C u = i → u = v := by
          intro u hu
          have hu_mem : u ∈ Finset.univ.filter (fun a => C a = i) := by
            rw [Finset.mem_filter]
            exact ⟨Finset.mem_univ u, hu⟩
          exact Finset.card_le_one_iff.mp hi hu_mem hv_mem
  4. For every other color j ≠ i, the vertex v has a neighbor of color j.

    For any color j ≠ i, the achromatic property of C (`hC.2`) guarantees that there exists an edge between some vertex u of color i and some vertex w of color j. Since v is the only vertex of color i, u must be v. Hence v is adjacent to w, meaning w is a neighbor of v with color j.

    lines 19–28

    uses Finset.ne_of_mem_erase, SimpleGraph.mem_neighborFinset

        have h_subset : ∀ j ∈ Finset.univ.erase i, ∃ w ∈ G.neighborFinset v, C w = j := by
          intro j hj
          have hji : j ≠ i := Finset.ne_of_mem_erase hj
          have hij : i ≠ j := hji.symm
          obtain ⟨u, w, hadj, hCu, hCw⟩ := hC.2 i j hij
          have hu : u = v := h_unique u hCu
          subst hu
          refine ⟨w, ?_, hCw⟩
          rw [SimpleGraph.mem_neighborFinset]
          exact hadj
  5. The number of colors satisfies k ≤ Δ(G) + 1, which is at most max{Δ(G) + 1, ⌊|V|/2⌋}.

    Since every color j ≠ i appears on some neighbor of v, the set of the other k - 1 colors is contained in the image under C of the neighborhood of v. Comparing cardinalities shows k - 1 ≤ deg(v). Since deg(v) ≤ Δ(G) by `G.degree_le_maxDegree`, we obtain k ≤ Δ(G) + 1, and transitivity with `le_max_left` finishes this case.

    lines 29–39

    uses Finset.mem_image_of_mem, Finset.card_le_card, Finset.card_image_le, SimpleGraph.card_neighborFinset_eq_degree, Finset.card_erase_of_mem, Finset.mem_univ, Finset.card_univ, Fintype.card_fin, G.degree_le_maxDegree, le_trans, le_max_left

        have h_card_le : (Finset.univ.erase i).card ≤ (G.neighborFinset v).card := by
          have : Finset.univ.erase i ⊆ (G.neighborFinset v).image C := by
            intro j hj
            obtain ⟨w, hw, rfl⟩ := h_subset j hj
            exact Finset.mem_image_of_mem C hw
          exact (Finset.card_le_card this).trans Finset.card_image_le
        rw [SimpleGraph.card_neighborFinset_eq_degree] at h_card_le
        rw [Finset.card_erase_of_mem (Finset.mem_univ i), Finset.card_univ, Fintype.card_fin] at h_card_le
        have h_deg : G.degree v ≤ G.maxDegree := G.degree_le_maxDegree v
        have hk : k ≤ G.maxDegree + 1 := by omega
        exact le_trans hk (le_max_left _ _)
  6. In the second case, every color class has cardinality at least 2.

    Because the first case does not hold, no color class has size at most 1, which means every color class has cardinality strictly greater than 1, hence at least 2.

    lines 40–43

      · have h2 : ∀ i : Fin k, 2 ≤ (Finset.univ.filter (fun a => C a = i)).card := by
          intro i
          have : ¬ (Finset.univ.filter (fun a => C a = i)).card ≤ 1 := fun hle => h ⟨i, hle⟩
          omega
  7. The total number of vertices |V| is the sum of the cardinalities of all k color classes.

    Partitioning the finite vertex set V into the fibers of the coloring map C via `Finset.card_eq_sum_card_fiberwise` expresses |V| as the sum of |C⁻¹(b)| over all colors b ∈ Fin k.

    lines 44–45

    uses Finset.card_eq_sum_card_fiberwise, Finset.mem_univ

        have h_sum : Fintype.card V = ∑ b : Fin k, (Finset.univ.filter (fun a => C a = b)).card := by
          exact Finset.card_eq_sum_card_fiberwise (f := C) (fun _ _ => Finset.mem_univ _)
  8. The number of colors satisfies k ≤ ⌊|V|/2⌋, which is at most max{Δ(G) + 1, ⌊|V|/2⌋}.

    Summing the lower bound |C⁻¹(b)| ≥ 2 over all k colors yields 2k ≤ |V|. In natural numbers, this implies k ≤ |V| / 2, which is bounded by the maximum via `le_max_right`.

    lines 46–53

    uses Finset.sum_le_sum, Finset.sum_const, Finset.card_univ, Fintype.card_fin, smul_eq_mul, le_trans, le_max_right

        have h_le : (∑ b : Fin k, 2) ≤ ∑ b : Fin k, (Finset.univ.filter (fun a => C a = b)).card := by
          apply Finset.sum_le_sum
          intro i _
          exact h2 i
        rw [Finset.sum_const, Finset.card_univ, Fintype.card_fin, smul_eq_mul] at h_le
        rw [← h_sum] at h_le
        have hk : k ≤ Fintype.card V / 2 := by omega
        exact le_trans hk (le_max_right _ _)
csSup_le'
If `a` is an upper bound of a set `s`, then the supremum `sSup s` is at most `a`.
Finset.mem_filter
An element `a` belongs to `{x ∈ s | p x}` if and only if `a ∈ s` and `p a` holds.
Finset.mem_univ
Every element of a finite type belongs to the universal finset `Finset.univ`.
Finset.card_le_one_iff.mp
If a finite set has cardinality at most 1, any two elements in it are equal.
Finset.ne_of_mem_erase
If `b` belongs to `s.erase a`, then `b ≠ a`.
SimpleGraph.mem_neighborFinset
A vertex `w` is in `G.neighborFinset v` if and only if `v` and `w` are adjacent.
Finset.mem_image_of_mem
If `a ∈ s`, then `f a` is in the image of `s` under `f`.
Finset.card_le_card
If `s ⊆ t`, then `|s| ≤ |t|`.
Finset.card_image_le
The cardinality of the image `f(s)` is at most the cardinality of `s`.
SimpleGraph.card_neighborFinset_eq_degree
The number of neighbors in `G.neighborFinset v` equals the vertex degree `G.degree v`.
Finset.card_erase_of_mem
Removing an element `a ∈ s` from a finite set `s` decreases its cardinality by 1.
Finset.card_univ
The cardinality of `Finset.univ` for a type `α` equals `Fintype.card α`.
Fintype.card_fin
The cardinality of the finite type `Fin n` is `n`.
G.degree_le_maxDegree
The degree of any vertex `v` is at most the maximum degree `G.maxDegree`.
le_trans
Inequality is transitive: if `a ≤ b` and `b ≤ c`, then `a ≤ c`.
le_max_left
Any element `a` is at most `max a b`.
Finset.card_eq_sum_card_fiberwise
The cardinality of a set partitioned fiberwise by a function `f` equals the sum of the cardinalities of the fibers.
Finset.sum_le_sum
If `f i ≤ g i` for all `i ∈ s`, then the sum of `f` over `s` is at most the sum of `g` over `s`.
Finset.sum_const
The sum of a constant `b` over a finite set `s` equals `|s| • b`.
smul_eq_mul
Scalar multiplication of natural numbers coincides with ordinary multiplication.
le_max_right
Any element `b` is at most `max a 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

theorem simple_graph_achromatic_number_le_max_degree_or_half {V : Type*} [Fintype V]    [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] :    simple_graph_achromatic_number G ≤ max (G.maxDegree + 1) (Fintype.card V / 2) := by  dsimp [simple_graph_achromatic_number]  apply csSup_le'  rintro k ⟨C, hC⟩  by_cases h : ∃ i : Fin k, (Finset.univ.filter (fun a => C a = i)).card ≤ 1  · obtain ⟨i, hi⟩ := h    obtain ⟨v, hv⟩ := hC.1 i    have hv_mem : v ∈ Finset.univ.filter (fun a => C a = i) := by      rw [Finset.mem_filter]      exact ⟨Finset.mem_univ v, hv⟩    have h_unique : ∀ u, C u = i → u = v := by      intro u hu      have hu_mem : u ∈ Finset.univ.filter (fun a => C a = i) := by        rw [Finset.mem_filter]        exact ⟨Finset.mem_univ u, hu⟩      exact Finset.card_le_one_iff.mp hi hu_mem hv_mem    have h_subset : ∀ j ∈ Finset.univ.erase i, ∃ w ∈ G.neighborFinset v, C w = j := by      intro j hj      have hji : j ≠ i := Finset.ne_of_mem_erase hj      have hij : i ≠ j := hji.symm      obtain ⟨u, w, hadj, hCu, hCw⟩ := hC.2 i j hij      have hu : u = v := h_unique u hCu      subst hu      refine ⟨w, ?_, hCw⟩      rw [SimpleGraph.mem_neighborFinset]      exact hadj    have h_card_le : (Finset.univ.erase i).card ≤ (G.neighborFinset v).card := by      have : Finset.univ.erase i ⊆ (G.neighborFinset v).image C := by        intro j hj        obtain ⟨w, hw, rfl⟩ := h_subset j hj        exact Finset.mem_image_of_mem C hw      exact (Finset.card_le_card this).trans Finset.card_image_le    rw [SimpleGraph.card_neighborFinset_eq_degree] at h_card_le    rw [Finset.card_erase_of_mem (Finset.mem_univ i), Finset.card_univ, Fintype.card_fin] at h_card_le    have h_deg : G.degree v ≤ G.maxDegree := G.degree_le_maxDegree v    have hk : k ≤ G.maxDegree + 1 := by omega    exact le_trans hk (le_max_left _ _)  · have h2 : ∀ i : Fin k, 2 ≤ (Finset.univ.filter (fun a => C a = i)).card := by      intro i      have : ¬ (Finset.univ.filter (fun a => C a = i)).card ≤ 1 := fun hle => h ⟨i, hle⟩      omega    have h_sum : Fintype.card V = ∑ b : Fin k, (Finset.univ.filter (fun a => C a = b)).card := by      exact Finset.card_eq_sum_card_fiberwise (f := C) (fun _ _ => Finset.mem_univ _)    have h_le : (∑ b : Fin k, 2) ≤ ∑ b : Fin k, (Finset.univ.filter (fun a => C a = b)).card := by      apply Finset.sum_le_sum      intro i _      exact h2 i    rw [Finset.sum_const, Finset.card_univ, Fintype.card_fin, smul_eq_mul] at h_le    rw [← h_sum] at h_le    have hk : k ≤ Fintype.card V / 2 := by omega    exact le_trans hk (le_max_right _ _)
See it in the graphDiscuss this resultChallenge it