Proper vertex colourings and chromatic number

Let $G=(V,E)$ be a finite simple graph (A finite simple graph is a finite vertex set together with a set of two-element vertex subsets) and let $k\in \mathbb{N}$. A proper $k$-vertex-colouring is a function

$c:V⟶k$

such that $c(u)\mathrm{\ne }c(v)$ whenever $\{u,v\}\in E$. Its fibres are the colour classes. The graph is $k$-colourable when such a function exists.

The chromatic number of $G$ is

$\chi (G):=\min \{k\in \mathbb{N}:G\text{ is }k\text{-colourable}\}\mathrm{.}$

This minimum exists. Since $V$ is finite, there is a bijection $b:V\to \mathrm{\mid }V\mathrm{\mid }$ (The cardinality $\mid A\mid$ of a finite set), and $b$ is a proper $\mathrm{\mid }V\mathrm{\mid }$-colouring because adjacent vertices are distinct. The displayed set of admissible natural numbers is therefore nonempty, so it has a least element by The well-ordering principle.

The null graph has $V=\mathrm{\varnothing }$. Its unique empty function $\mathrm{\varnothing }\to 0$ is a proper $0$-colouring, so $\chi (G)=0$. Conversely, a nonnull graph has no function from its nonempty vertex set to $0=\mathrm{\varnothing }$, and hence has positive chromatic number. Colours are labels only: composing a proper colouring with a bijection of its colour set changes no adjacency condition.