simple_graph_achromatic_number_le_max_degree_or_half
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
- simple_graph_achromatic_numberχ_a(G) is the maximum number of colours in an achromatic colouring of G.
- simple_graph_coloring_is_achromaticA proper vertex colouring with k colours is achromatic if all k colours are used and there is at least one edge between each pair of…
- Used by 3
- cubic_paley_graph_zmod_nineteen_achromatic_numberThe cubic Paley graph G_3(19) has achromatic number 9 = (19 − 1)/2, the upper bound, above the value (19 + 2)/3 = 7 conjectured for large q.
- cubic_paley_graph_zmod_thirteen_achromatic_numberThe cubic Paley graph G_3(13) has achromatic number 6 = (13 − 1)/2, the upper bound, above the value (13 + 2)/3 = 5 conjectured for large q.
- cubic_paley_graph_zmod_thirty_one_achromatic_numberThe cubic Paley graph G_3(31) has achromatic number 15 = (31 − 1)/2, the upper bound, above the value (31 + 2)/3 = 11 conjectured for…
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⌋.
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.
uses
csSup_le'dsimp [simple_graph_achromatic_number] apply csSup_le' rintro k ⟨C, hC⟩
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.
by_cases h : ∃ i : Fin k, (Finset.univ.filter (fun a => C a = i)).card ≤ 1
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`.
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
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.
uses
Finset.ne_of_mem_erase,SimpleGraph.mem_neighborFinsethave 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
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.
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_lefthave 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 _ _)
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.
· 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
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.
uses
Finset.card_eq_sum_card_fiberwise,Finset.mem_univhave 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 _)
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`.
uses
Finset.sum_le_sum,Finset.sum_const,Finset.card_univ,Fintype.card_fin,smul_eq_mul,le_trans,le_max_righthave 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`.
- In Lean, division `/ 2` on natural numbers denotes integer division (the floor ⌊|V|/2⌋).
- The linear integer arithmetic tactic `omega` handles the arithmetic deduction of `k ≤ Δ(G) + 1` from `k - 1 ≤ deg(v) ≤ Δ(G)` (line 38), and of `k ≤ |V| / 2` from `2 * k ≤ |V|` (line 52).
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.
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 _ _)