Let $G=(V,E)$ be a connected graph .
Let $C(v)$ denote a set of possible colors for the vertex $v \in V$. Such that $|C(v)|\ge deg(v)$ and for at least one vertex $w \in V$ $|C(w)|\gt deg(w)$
Prove there exists a vertex coloring of $G$ such that for every $(u,v) \in E$ $\;u$ and $v$ have different colors
My idea: I thought I could prove this using induction but if I do induction over $|V|$ I don't know how to continue (How to apply the induction to a subgraph)
Would appreciate any help
Let $G'=G-w$. Each connected component of $G'$ has less edges than $G$ and has at least one former neighbour $v$ of $w$. As $\deg v$ got decreased, we have $|C(v)|>\deg v$ in $G'$. So by induction hypothesis (each component of) $G'$ can be coloured without monochromatic edges. By picking a colour for $w$ that is not among the $\deg w<|C|$ dolours of its neighbours, we obtain a colouring for $G$ wihout monochromatic edges.