Proof that the chromatic number of a complete bipartite graph is 2

Proof

We show that $K_{m,n}$ is $2$-colourable but not $1$-colourable.

1. Let $m, n \ge 1$. Let the complete bipartite graph $K_{m,n}$ have vertex set $A \sqcup B$, where $\abs{A} = m$ and $\abs{B} = n$.
2. Define $c(a) = 1$ for $a \in A$ and $c(b) = 2$ for $b \in B$.
3. Every edge joins a vertex of $A$ to a vertex of $B$, so its ends get the different colours $1$ and $2$. Hence $c$ is a colouring, and $K_{m,n}$ is $2$-colourable.
4. Since $m, n \ge 1$, there are vertices $a \in A$ and $b \in B$, and they are adjacent.
5. A colouring with colours in $\set{1}$ would give $a$ and $b$ the same colour $1$. So $K_{m,n}$ is not $1$-colourable.
6. A colouring with colours in the empty set exists only when there are no vertices. Since $K_{m,n}$ has vertices, it is not $0$-colourable.
7. By Steps 3, 5 and 6, the smallest $k$ such that $K_{m,n}$ is $k$-colourable is $2$. So the chromatic number of $K_{m,n}$ is $2$.