Let G be a graph satisfying the following conditions:
(1) $\chi(G)=5$ and (2) $\chi(G-v) =4$ for each vertex $v \in G$
Show that $\delta(G) \geq 4$.
Answer given:
Suppose $\delta(G) \leq 3.$ Let v be a vertex in G such that $d(v)=\delta(G)$. Since $\chi(G-v) = 4$, there is a colouring $\theta: V(G-v) \longrightarrow \{1,2,3,4\}$. Since $d(v) = \delta(G) \leq 3$, there is at least one colour, say 4, not used to colour the neighbours of v. Extend $\theta$ to colour G by colouring v the colour 4. This gives a 4-colouring of G. Thus, $\chi(G) \leq 4$, which is a contradiction. Hence, $\delta(G) \geq 4$.
I have difficulty understanding the solution. I don't understand this part where it says "since $d(v) = \delta(G) \leq 3$, there is at least one colour, say 4, not used to colour the neighbours of v."
Suppose $\chi(G)=5$ and $\chi(G-v)=4, \forall v \in V$. We need to show that every vertex has degree at least 4. By way of contradiction, suppose some vertex $w$ has degree at most 3, i.e. $w$ has at most three neighbors. Recall that for any vertex $v$, $G-v$ can be 4-colored. In particular, $G-w$ can be 4-colored, using colors $\{1,2,3,4\}$ say. In other words, we begin to color $G$ by coloring all its vertices except $w$. After all vertices in $G-w$ have been colored, we also color $w$. But $w$ has at most three neighbors, and hence among the four colors used so far one color is not assigned to a neighbor of $w$. This color can be assigned to $w$. Thus, it is possible to properly color all vertices of $G$ using only four colors. This contradicts the hypothesis that $\chi(G)=5$. Hence the assumption that some vertex has degree at most 3 is false.