Q: Proving G is d-colorable I'm studying graph theory, coloring at the moment. I'm stuck with a proof of the following exercise:
Let $G = (V, E)$ be a connected graph and let $v \in V$ be such that $deg(v)\lt d$. If $deg(w)\le d$ for all $w \in V-{v}$, then $G$ is $d$-colorable.
I have an idea that I could use Brooks' Theorem but I'm not really sure. I'd appreciate it if someone could give me a hand here
 A: We can do this by induction on the number of vertices, for a fixed $d\geq1$.
Clearly this is true for a graph with a single vertex.
For the induction step, assume the statement is true for all connected graphs with $n-1$ or fewer vertices ($n\geq 1$), all with degree at most $d$ and at least one vertex with degree strictly less than $d$. Take any connected graph $G=(V,E)$ with $|V|=n$, maximum degree $d$ and at least one vertex $v$ with degree strictly less than $d$.
If we remove $v$ and any edges going to $v$ from $G$, we will be left with a graph $G'$ with $n-1$ vertices, maximal degree $d$, and because $v$ had at least one neighbor, there is at least one vertex in $G'$ with degree strictly less than $d$ (namely, $v$'s previous neighbors).
Note that $G'$ might not be connected, but we may use the induction hypothesis on each connected component, to show that it can be coloured using at most $d$ colours.
Now add $v$ back in. It has less than $d$ neighbors, so at least one colour is available to use on $v$. This finishes the proof.

If you want to use Brooks's theorem instead, note that the degree requirement neatly takes care of the cycle graph and complete graph exceptions in that theorem:

*

*If $G$ is a cycle graph, then the requirement that there is at least one vertex with degree strictly less than $d$ means $d\geq3$, and cycle graphs are always 3-colorable

*If $G$ is a complete graph, then the requirement that there is at least one vertex with degree strictly less than $d$ means there are at most $d$ vertices, so you can give each vertex its own colour

For any other graph, Brooks's theorem says exactly that since the maximal degree is (at most) $d$, the graph is $d$-colourable.
