AFTD Auto-Formalizing Theoretical Domains

graph_11_chromatic_number

theoremverifiedformalization

The chromatic number of the simple graph G_11 equals 3.

Statement

theorem graph_11_chromatic_number : graph_11.chromaticNumber = 3
Formalizes
arXiv:2610.39430 Lemma 3.3
Verified
31 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • graph_11The 11-vertex simple graph G_11 on Fin 11 consisting of a base 4-cycle 0-1-2-3-0, four caps 4, 5, 6, 7 adjacent to consecutive base pairs,…
Used by 2

Read back from the Lean

The chromatic number of the simple graph graph_11 on the vertex set Fin 11 is equal to 3.

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 shows that the chromatic number of G_11 is 3 by establishing matching upper and lower bounds. The upper bound graph_11.chromaticNumber ≤ 3 is proved by exhibiting an explicit proper 3-coloring with color classes {4, 5, 6, 7}, {0, 2, 8, 9}, and {1, 3, 10}, verified by exhaustive finite case analysis over all pairs of vertices. The lower bound 3 ≤ graph_11.chromaticNumber is proved by exhibiting a 3-clique on vertices {4, 8, 10} and checking pairwise adjacency by finite case analysis.

  1. The equality of chromatic numbers reduces to proving the upper bound graph_11.chromaticNumber ≤ 3 and the lower bound 3 ≤ graph_11.chromaticNumber.

    By antisymmetry of the partial order on extended natural numbers (le_antisymm), two numbers are equal if each is less than or equal to the other.

    line 3

    uses le_antisymm

      refine le_antisymm ?_ ?_
  2. To prove the upper bound graph_11.chromaticNumber ≤ 3, it suffices to show that the explicit 3-coloring assigns different colors to adjacent vertices.

    By SimpleGraph.Colorable.chromaticNumber_le, a graph with a valid 3-coloring has chromatic number at most 3. We construct a candidate 3-coloring using SimpleGraph.Coloring.mk with the color assignment ![1, 2, 1, 2, 0, 0, 0, 0, 1, 1, 2], partitioning the vertices into color classes {4, 5, 6, 7}, {0, 2, 8, 9}, and {1, 3, 10}.

    lines 5–7

    uses SimpleGraph.Colorable.chromaticNumber_le, SimpleGraph.Coloring.mk

        refine SimpleGraph.Colorable.chromaticNumber_le
          (show graph_11.Colorable 3 from ?_)
        refine ⟨SimpleGraph.Coloring.mk (fun v : Fin 11 => ![1, 2, 1, 2, 0, 0, 0, 0, 1, 1, 2] v) ?_⟩
  3. The proposed coloring is proper: adjacent vertices always receive different colors, concluding the upper bound. automation

    Assuming two vertices v and w are adjacent in graph_11, we perform an exhaustive case analysis over all 11 possibilities for v and all 11 possibilities for w. In each case, simplifying with the definition of graph_11 reveals that either the adjacency hypothesis is contradictory or the two vertices have different colors.

    lines 8–9

    uses graph_11, SimpleGraph.fromRel

        intro v w h
        fin_cases v <;> fin_cases w <;> simp [graph_11, SimpleGraph.fromRel] at h ⊢
  4. The lower bound 3 ≤ graph_11.chromaticNumber holds because vertices 4, 8, and 10 form a triangle. automation

    We apply SimpleGraph.le_chromaticNumber_of_pairwise_adj to the three vertices 4, 8, and 10 indexed by Fin 3. The cardinality condition 3 ≤ |Fin 3| is verified immediately by simplification. For pairwise adjacency, we introduce distinct indices i and j, split into cases over all 3 choices for i and j, and verify in each case by simplification from the definition of graph_11 that the corresponding vertices are adjacent.

    lines 11–13

    uses SimpleGraph.le_chromaticNumber_of_pairwise_adj, graph_11, SimpleGraph.fromRel

        exact SimpleGraph.le_chromaticNumber_of_pairwise_adj (by simp) (fun i : Fin 3 => ![4, 8, 10] i) (by
          intro i j hij
          fin_cases i <;> fin_cases j <;> simp_all [graph_11, SimpleGraph.fromRel])
le_antisymm
Antisymmetry of a partial order: if a ≤ b and b ≤ a, then a = b.
SimpleGraph.Colorable.chromaticNumber_le
If a graph has an n-coloring, its chromatic number is at most n.
SimpleGraph.Coloring.mk
Constructs a proper coloring of a graph from a color assignment function and a proof that adjacent vertices receive different colors.
graph_11
The definition of the 11-vertex graph G_11.
SimpleGraph.fromRel
Builds a simple graph from a symmetric, irreflexive binary relation.
SimpleGraph.le_chromaticNumber_of_pairwise_adj
If a graph contains a family of n pairwise adjacent vertices, its chromatic number is at least n.

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

/-- The chromatic number of G_11 is 3. -/theorem graph_11_chromatic_number : graph_11.chromaticNumber = 3 := by  refine le_antisymm ?_ ?_  · -- upper bound: the three classes {4,5,6,7}, {0,2,8,9}, {1,3,10} form a 3-coloring    refine SimpleGraph.Colorable.chromaticNumber_le      (show graph_11.Colorable 3 from ?_)    refine ⟨SimpleGraph.Coloring.mk (fun v : Fin 11 => ![1, 2, 1, 2, 0, 0, 0, 0, 1, 1, 2] v) ?_⟩    intro v w h    fin_cases v <;> fin_cases w <;> simp [graph_11, SimpleGraph.fromRel] at h ⊢  · -- lower bound: {4, 8, 10} is a triangle    exact SimpleGraph.le_chromaticNumber_of_pairwise_adj (by simp) (fun i : Fin 3 => ![4, 8, 10] i) (by      intro i j hij      fin_cases i <;> fin_cases j <;> simp_all [graph_11, SimpleGraph.fromRel])
See it in the graphDiscuss this resultChallenge it