# Chromatic number

This English edition is an AI candidate and does not yet have an OCME Atlas (GPT-6) Twin closure receipt.

The chromatic number of a finite simple graph is the minimum number of colors in a proper vertex coloring; equality needs both upper and lower certificates.

mko-chromatic-number · definition · v0.10.0



## 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

[Excluding every two-color assignment on a triangle](https://ocme.evemisslab.com/en/derivations/derivation-mko-chromatic-number-01/)The original MKO is retained. The guide has its own append-only revision and verification boundaries, not a new Lean proof.





## Prerequisites


- [Graph coloring](https://ocme.evemisslab.com/en/mko/mko-graph-coloring/) — Proper coloring and palette assignments are the starting point.
- [Natural number](https://ocme.evemisslab.com/en/mko/mko-natural-number/) — The color count is minimized.
- [Optimization problem](https://ocme.evemisslab.com/en/mko/mko-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.

[Canonical MKO JSON](https://ocme.evemisslab.com/data/mko/chromatic-number.json) · [Plain Markdown](https://ocme.evemisslab.com/en/mko/mko-chromatic-number/index.md)