Graph Theory—Number of ways to color the graph $C_4$ with $r$ colors 
Question: How many ways can you properly color the cycle C$_{4}$ with
  r colors? And in general, how many ways are there to properly color the cycle C$_{n}$ with r colors?


Thought process: 


*

*If I begin at the top left vertex, I have a choice of r colors. 

*Then, if I move to the top right vertex, I have $r$ — 1 options to choose from. 

*If I next move to the bottom right vertex, I can't use the same color I used on the top right vertex or the top left (since I have to use all $r$ colors—or do I?), so I would have $r-2$ choices.

*For the bottom left vertex, with similar reasoning as the previous step, I would have $r — 3$ choices.

*Finally, to determine the total number of ways to color $C_{4}$ with $r$ colors, I multiply each of these numbers together, giving
$(r)(r — 1)(r — 2)(r — 3)$
So, am I spouting total nonsense or am I on to something? For $C_{4}$ does $r$ have to be at least a certain number? Whatever the right answer is, I'm assuming finding the number of ways to color $C_{n}$ with $r$ colors is similar?
 A: For $r=2$ we have $2$ proper colorings, i.e. $(v_1,v_2,v_3,v_4)$ can be $(c_1,c_2,c_1,c_2)$ or $(c_2,c_1,c_2,c_1)$ but according to your formula $(r)(r — 1)(r — 2)(r — 3)$ we find $0$ colorings. So it is not correct.
In order to find $c_4(r)$ i.e. the number of proper colorings of $C_4$ with $r$ colors, we consider two distinct cases.
1) Vertex 1 and vertex 3 have the same color: we choose such color in $r$ ways and we have $(r-1)$ choices for vertex 2 and $(r-1)$ choices for vertex 4. Thus we obtain
$$r\cdot (r-1)^2.$$
2) Vertex 1 and vertex 3 have two different colors: we choose such colors in $r(r-1)$ ways and we have $(r-2)$ choices for vertex 2 and $(r-2)$ choices for vertex 4. Thus we obtain: 
$$r\cdot (r-1)\cdot (r-2)^2$$
Hence the total number is
$$c_4(r)=r\cdot (r-1)^2+r\cdot (r-1)\cdot (r-2)^2=r(r-1)(r^2-3r+3).$$
Can you extend this approach and find $c_5(r)$?
What about the number $c_n(r)$ of proper colorings  of $C_n$ with $r$ colors? 
P.S. For the general case, not that the formulas 1) and 2) can be read as $c_{2}(r)\cdot (r-1)$ and $c_{3}(r)\cdot (r-2)$, respectively.
