Harvard-MIT Math Tournament

Solution:

We prove the claim by induction on $n$. The case $n = 3$ was addressed in (a).

Let $n \geq 3$ and suppose $G$ is a graph with chromatic number $n$ containing no $n$-cliques. We produce a graph $G'$ with chromatic number $n+1$ containing no $(n+1)$-cliques as follows. Add a vertex $v$ to $G$, and add an edge from $v$ to each vertex of $G$.

To see this graph has chromatic number $n+1$, observe that any coloring of the vertices of $G'$ restricts to a valid coloring of the vertices of $G$. So at least $n$ distinct colors must be used among the vertices of $G$. In addition, another color must be used for $v$. By coloring $v$ a new color, we have constructed a coloring of $G'$ having $n+1$ colors.

Lastly, any $(n+1)$-clique in $G'$ must have at least $n$ vertices in $G$ which form an $n$-clique, which is impossible. Therefore, $G'$ has no $(n+1)$-cliques.