It suffices to establish the following: Claim. Let $k$ be a positive integer and $G$ be a graph on $n>k$ vertices, all of degree at least $1$, with minimum number $k$ of colours required. Suppose that merging one pair or two pairs of vertices results in a graph which can be coloured in $k-1$ or less colours. Then every vertex of $G$ has degree at least $k$. Consider a vertex $v$ and denote its neighbours by $v_1,\ldots,v_{\deg v}$. (Note that, by assumption, $v$ has at least one neighbour.) To begin with, merge $v$ with $v_i$, denote the new vertex by $v_0$, and colour the obtained graph in $k-1$ colours. Unless all $k-1$ colours appear in $S_1 = \{v_0,v_1,\ldots,v_{i-1},v_{i+1},\ldots,v_{\deg v}\}$, we can get a $(k-1)-$colouring of $G$ by assigning the colour of $v_0$ to $v_i$ and an unused colour (from the $k-1$ available) to $v$, thus contradicting the assumption that $k$ is the minimum amount of required colours. Now since the above set has size $\deg v$, we deduce $\deg v \geq k-1$. What is more, if all $k-1$ colours appear in $S_1$ we can still get a $k$-colouring of $G$ in which $v$ is the \textit{only} vertex of colour $k$, by taking the above $k-1$ colouring of the contracted graph (with $v_i$ having the colour of $v_0$) and assigning colour $k$ to $v$. Next, we show that $\deg v \geq k$ or $v_1,\ldots,v_{\deg v}$ induce a complete subgraph. Suppose $v_iv_j \not \in E(G)$ and merge $v$ with $v_i$, giving the next vertex $w$, and then $w$ with $v_j$, denoting the newest vertex by $v_0$, and then colour the resulting graph in $k-1$ colours. Unless all $k-1$ colours appear in $S_2 = \{v_0,v_1,\ldots,v_{\deg v}\}\setminus\{v_i,v_j\}$, we can get a $(k-1)$-colouring of $G$ by assigning the colour of $v_0$ to $v_i$ and $v_j$ and an unused colour (from the $k-1$ available) to $v$, thus contradicting the assumption that $k$ is the minimum amount of required colours. Now since the above set has size $\deg v - 1$, we deduce $\deg v \geq k$. What is more, if all $k-1$ colours appear in $S_2$ we can still get a $k$-colouring of $G$ in which $v$ is the \textit{only} vertex of colour $k$, by taking the above $k-1$ colouring of the contracted graph (with $v_i$ and $v_j$ having the colour of $v_0$) and assigning colour $k$ to $v$. To prove the main statement, we proceed by assuming there is a vertex $v$ of degree less than $k$ and obtaining a contradiction. By the above we must have $\deg v = k-1$, the neighbourhood of $v$ induces a complete subgraph and we can work with a colouring of $G$ in which $v$ is the only vertex of colour $k$. It remains to prove that there are no vertices of $G$ which are not neighbours of $v$ -- then we would conclude that $G$ is a complete graph on $k$ vertices, which would contradict $n>k$. Suppose, for contradiction, that there is a vertex $w$ which is not a neighbour of $v$. By the first two paragraphs, we have two cases: \begin{itemize} \item We treat $\deg w = k-1$ and that $k-1$ distinct colours appear among the neighbours of $w$. But since $v$ is the only vertex with the $k$-th colour, there is no available colour for $w$ (among the $k$ we are working with), a contradiction with the assumption that $k$ colours are sufficient. \item We treat $\deg w = k$. If there are two neighbours of $w$ which are not joined by an edge, then by the second paragraph we have that $k-1$ distinct colours appear among the neighbours of $w$ and this gives a contradiction as in the previous case. So we see that every two neighbours of $w$ are joined by an edge and so $w$ and its $k$ neighbours induce a complete subgraph on $k+1$ vertices -- but this one cannot be coloured with at most $k$ colours and we get a contradiction with the assumption that $k$ colours are sufficient. \end{itemize} This completes the proof.