If you are familiar with the notion of Chromatic Polynomial, this is an easy problem. You just calculate the Chromatic Polynomial of the Cycle $C_5$ :
$$C_5=P_5-C_4 \,.$$
If not, here is the standard approach.
The strategy: You color vertices in order. You have 5 choices for vertex 1, 4 for vertex 2, 4 for vertex 3 ...
The problem: How many choices do we have for vertex 5? Note that the answer depends on whether vertices 1 and 4 have the same color or different colors.
The solution: Split the problem in 2: count separately the number of ways of coloring $C_5$ such that $1$ and $4$ have the same color and the number of ways of coloring $C_5$ such that $1$ and $4$ have different colors. Note that in the second case you'll need to split again in 2 and 4 have same or different colors.
This paper (web archive) explains everything nicely.
In the nutshell:
- Draw a graph consisting of four disconnected vertices R, G, Y, and W.
- For each cube, find all 3 pairs of sides that are opposite to each other
- For each (A, B) pair of sides, add an {A, B} edge to the graph and label the edge with the # of the cube.
For example, for the Cube 1, the opposite sides are (Y, G), (W, Y) and (R, W). You connect those on the original (1) graph and label each of them with "1".
After you are done with all cubes, you just have to find two cycles that don't share an edge, that go over every vertex R, G, Y and W exactly once that use differently labeled edges 1, 2, 3 and 4 exactly once. You can split a cycle in several circuits.
For example, for the problem given in my original question, I have got next two cycles (one of which contains multiple circuits):
- R - 3 - W - 2 - G - 1 - Y - 4 - R.
- W - 4 - W. G - 3 - G. R - 1 - Y - 2 - R.
From this we can see that cube 1 will have two opposite sides G and Y as its faces from (1) and 2 another opposite sides R and Y as its faces from (2). 2 would have W, G and Y, R. 3 would have R, W and G, G. 4 would have W, W and Y, R.
Graphically, something like that:
R Y G W
G 3 Y W 2 G R 3 W Y 4 R
Y R G W
That is all, we got a column of cumes with different colors on each of 4 sides.
Best Answer
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.