Here's the full question:
Let G be a graph where every vertex has $degree\geq 3$. Prove or give a counterexample to the assertion that at least three colors are needed to color the vertices of G.
Been trying to figure this out for the past few hours now. I mean, we know that the largest $K_n$ graph contained within $G$ will be a $K_3$, so it follows then that we must have a chromatic number $\chi(G) \geq 3$. I feel, though, that this is stating what we need to be prove and is thus a very hollow argument.
If anyone could give a hand, would be much obliged.
Try $K_{n,n}$ the complete bipartite graph on $n$ and $n$ vertices where $n \ge 3$.