Hint: Let $V(G)=\{v_1,v_2,\dots,v_\nu\}$ where $v_i$ is a vertex of degree $d_i.$ Now color the vertices $v_1,v_2,\dots,v_\nu$ in that order: $v_1$ first, $v_2$ second and so on. Now, at the $i^{\text{th}}$ step, when vertex $v_i$ is to be colored, what is an upper bound for the number of neighbors of $v_i$ which have already been colored?
First we establish the upper bound by exhibiting a 3-(total-)coloring for $C_n$ when $3\mid n$ and a 4-coloring for all $n$.
When $n\mid 3$ color the vertices red, green, blue cyclically.
Color the edge between two vertices with the only color that is not used on its endpoints. This is a proper total coloring with 3 colors (verify!).
When $n$ is even we alternately color the vertices with red and green, and we alternately color the edges with blue and yellow.
This is a proper total coloring with 4 colors (verify!).
When $n$ is odd we go clockwise around the cycle and start coloring vertices alternately with red and green. The last vertex would cause two adjacent red vertices, so we color it blue instead. Now we walk around the cycle again and when we go from a red to a green vertex we color the edge blue, when we go from a green to a red vertex we color the edge blue, when we go from a green to a blue vertex (only once) we color the edge red and when we go from a blue to a red vertex (only once) we color the edge green.
This is a proper total coloring with 4 colors (verify!).
Since $\chi''(G)\geq\Delta(G)+1=3$ we are already done with the case $3\mid n$.
For the last part we need to show that no proper 3-total-coloring is possible,
unless $n$ is a multiple of 3.
Let $v_1,\ldots,v_n$ be the vertices of $C_n$ and assume we have a proper 3-coloring. $v_1$, $v_2$ and edge $v_1v_2$ must have all different colors, say red, green, blue respectively. Now edge $v_2v_3$ cannot be green or blue, so it must be red. Vertex $v_3$ cannot be green or red, so it must be blue. Continuing this process you see that the entire coloring is forced and that we end up with a cyclic coloring of the vertices with period three just as we used above (verify!). Clearly this is only possible when $n$ is a multiple of 3.
Best Answer
A decision problem A is NP-hard means that if you can solve A in polynomial in input size, you can solve any NP problem in polynomial time (in input size). The mechanism to convert a problem B to a problem A (in polynomial time) is called a reduction from B to A.
3-COLOURABILITY
Input: A graph G
Question: Is G 3-colourable (i.e., is $\chi(G)\leq 3)$ ?
The problem 3-COLOURABILITY is NP-hard because there is a polynomial time reduction from 3-SAT to 3-COLOURABILITY and there is a reduction from SAT to 3-SAT. It is proven that if you can solve SAT in polynomial time, you can solve any NP problem in polynomial time (Cook's theorem). Hence, checking if chromatic number is at most 3 is hard and therefore finding chromatic number exactly must be hard as well.
Note: (Read this in case you get interested in reductions)
You can find a reduction from NAE SAT to 3-COLOURABILITY more easily (i think so).