Chromatic number

Mathematical statement

One proper k-coloring proves chi(G)≤k; equality also needs a valid exclusion of (k−1)-colorings. Complete small graphs are checked exhaustively for a lower bound and given an explicit coloring for an upper bound. A greedy result alone is not optimality evidence. The empty vertex graph has chi=0 and a nonempty edgeless graph has chi=1.

Representative formula (exact TeX)

chi(G)

Assumptions

• The complete finite loop-free simple undirected graph has vertices0 through n−1.
• Exact-number exercises use n≤9 and exhaust every smaller palette.

Symbol scope

• chi — chromatic number
• G — finite simple graph

Intuition, definition, and misconceptions

k-colorable means at most k colors, not exactly k required.

Equality combines a constructive upper certificate with a valid lower certificate.

Greedy coloring supplies only an upper-bound algorithm unless optimality is proved separately.

Finding a proper k-coloring does not by itself prove chi(G)=k.

Adopted derivation guide

The original MKO is retained. The guide has its own append-only revision and verification boundaries, not a new Lean proof.

Prerequisites

• Graph coloring — Proper coloring and palette assignments are the starting point.
• Natural number — The color count is minimized.
• Optimization problem — An upper bound and minimality are separate obligations.

Verification boundary

Exact search covers only complete explicitly supplied small finite graphs; no general complexity or approximation guarantee is made.

not_formalized

This does not mean the content is false; it means no replayable computational or formal evidence is registered yet.

Next obligation

Add perfect graphs and chromatic polynomials.

Same-source structured data

This page and the interactive view use the same object and existing language edition; this adds no proof or human review.