Let $k\geq 2$ be an integer and $G$ be a graph with chromatic number $k$. Suppose that any graph obtained by contracting one or two edges of $G$ has chromatic number at most $k-1$. Prove that either $G$ is complete or all of its vertices have degree at least $k$.
Progress: The natural way to logically approach this is to assume there is a vertex of degree less than $k$ and prove that $G$ is complete. If $v$ is such a vertex, then its neighbourhood must induce a complete graph.
In general, do you think that using some greedy algorithm for colourings, together with repeated uses of the above observation, would help here?
Best Answer
Let $v$ have neighbours $v_1,\ldots, v_{\deg (v)}$. We consider two reductions:
Reduction 1. Contract $v_iv$ and colour the resulting graph $G'$ with $k-1$ colours $c_1,\ldots c_{k-1}$. We can turn this into a $k$-colouring of $G$ by assigning the colour of the merged vertex $v_iv$ of $G'$ to $v_i$ in $G$ and assigning $c_k$ to $v$.
Note that in this $k$-colouring, $v$ is the only vertex of colour $c_k$. If any of the colours $c_1,\ldots, c_{k-1}$ were not used among $v_1,\ldots, v_{\deg v}$, we could use that colour for $v$ and would obtain a $(k-1)$-colouring, contradiction. We conclude that in particular $\deg v\ge k-1$.
Reduction 2. Suppose $v$ and its neighbours do not induce a complete graph as subgraph. In other words, there are neighbours $v_i,v_j$ of $v$ such that there is no edge $v_iv_j$. Contract $v_iv$ and $vv_j$ and colour the resulting graph with $k-1$ colours. We can turn this into a $k$-colouring of $G$ by assigning the colour of the merged vertex $v_ivv_j$ of $G'$ to $v_i$ and $v_j$ in $G$ and assigning $c_k$ to $v$.
As above, note that in this $k$-colouring, $v$ is the only vertex of colour $c_k$. If any of the colours $c_1,\ldots, c_{k-1}$ were not used among $v_1,\ldots, v_{\deg v}$, we could use that colour for $v$ and would obtain a $(k-1)$-colouring, contradiction. As $v_i$ and $v_j$ have the same colour, we can this time conclude that $\deg v\ge k$.
We use these result to show the desired claim about $G$: If all vertices have degree $\ge k$, we are done. So assume otherwise and pick one vertex $v$ of degree $<k$. Per reduction 1, we find that $\deg(v)=k-1$. Moreover, the subgraph induced by $v$ and its neighbours must be complete $K_k$ as otherwise we could apply reduction 2, contradicting the degree of $v$. If this $K_k$ is all of $G$, we are done. So assume otherwise and let $w$ we a vertex not in that $K_k$. Per reduction 1, there exists a $k$-colouring of $G$ where $w$ is the only vertex of colour $c_k$. This induces a $(k-1)$-colouring of the $K_k$ around $v$, contradiction.