Exercise 1682Combinatorics › Graph theoryL1Added 3 Nov 2026

Chromatic number

#chromatic number#coloring#clique

Statement

Define the chromatic number $\chi(G)$ and compute it for $K_n$ , $C_n$ (cycle of length $n$ ), and bipartite graphs.

Hint

$K_n$ needs $n$ colors; $C_n$ needs $2$ or $3$ depending on parity.

Show solutionHide solution

$K_n$ . All vertices pairwise adjacent, so $\chi(K_n)=n$ .

$C_n$ . If $n$ even, $C_n$ is bipartite, so $\chi=2$ . If $n$ odd, $\chi=3$ (2 colors alternate, but closing the cycle requires a third).

Bipartite. $\chi(G)=2$ if $G$ has at least one edge; $\chi=1$ if edgeless.

Conclusion. $\chi(K_n)=n$ , $\chi(C_n)=2$ (even $n$ ) or $3$ (odd $n$ ).