[Math] Cube color matching Graph Theory problem

coloringgraph theory

I'm trying to solve a problem:

Suppose you are given four cubes with each of the six faces painted with one of the colors red, white, green, or yellow. Use graph theory to place the cubes in a column of four such that all four different colors appear on each of the four sides of the column?

enter image description here

I have drawn 4 disjoint graph representing the cubes (each vertex having a degree 4 because sides of cube connect), but I don't see how can I apply either graph-coloring, matching theory, or just graph theory in this case.

One observation is that each of cubes can have only 3 possible combinations of sides, because there are 3 ways it can be placed. For example, Cube 1 has:

W R Y W
Y R G W
Y W G Y

All those letters can be rotated left and right as needed.

Another observation would be that the Cube 3 has 2 repeated colors regardless of how we place it, which restricts choices of other cubes a little.

Though I don't know if these observations help at all in solving it using Graph Theory.

Best Answer

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.

Related Solutions

[Math] How to find all proper colorings (four coloring) of a graph with a brute force algorithm

You can generate all 4 (or other number) colorings using Sage, an open source computer math system. You can use it free online without having to install it at http://www.sagenb.org/

If you can input your graph in Sage to the symbol G, then the following code will print all the graph G with all the different colorings

for C in sage.graphs.graph_coloring.all_graph_colorings(G, 4):
    G.plot(vertex_colors = C)

[Math] Painting a cube with 3 colors (each used for 2 faces).

This one can be done with the Polya Enumeration Theorem, which requires the cycle index $Z(G)$ of the face permutation group $G$ of the cube. We now enumerate the permutations from this group by their cycle structure.

There is the identity, which contributes $$a_1^6.$$ There are rotations about diagonals connecting opposite vertices, which contribute $$4 \times 2 \times a_3^2.$$ There are the rotations about an axis passing through the centers of opposite faces, which contribute $$3\times (2 a_1^2 a_4 + a_1^2 a_2^2).$$ Finally there are rotations about an axis passing through the midpoints of opposite edges, which contribute $$6\times a_2^3.$$ It follows that the cycle index is $$Z(G) = \frac{1}{24} a_1^6 + \frac{1}{3} a_3^2 + \frac{1}{4} a_1^2 a_4 + \frac{1}{8} a_1^2 a_2^2 + \frac{1}{4} a_2^3.$$ Substituting the three colors red, green, and blue into this cycle index we get $$Z(G)(R+G+B) = 1/24\, \left( R+G+B \right) ^{6}+1/4\, \left( R+G+B \right) ^{2} \left( {R}^{4} +{G}^{4}+{B}^{4} \right)\\ +1/8\, \left( R+G+B \right) ^{2} \left( {R}^{2}+{G}^{2 }+{B}^{2} \right) ^{2}+1/3\, \left( {R}^{3}+{G}^{3}+{B}^{3} \right) ^{2}+1/4\, \left( {R}^{2}+{G}^{2}+{B}^{2} \right) ^{3}.$$ Expanding this cycle index we obtain $${B}^{6}+{B}^{5}G+{B}^{5}R+2\,{B}^{4}{G}^{2}+2\,{B}^{4}GR+2\,{B}^{4}{R}^{2}+2\,{ B}^{3}{G}^{3}+3\,{B}^{3}{G}^{2}R+3\,{B}^{3}G{R}^{2}\\+2\,{B}^{3}{R}^{3}+2\,{B}^{2 }{G}^{4}+3\,{B}^{2}{G}^{3}R+6\,{B}^{2}{G}^{2}{R}^{2}+3\,{B}^{2}G{R}^{3}+2\,{B}^ {2}{R}^{4}\\+B{G}^{5}+2\,B{G}^{4}R+3\,B{G}^{3}{R}^{2}+3\,B{G}^{2}{R}^{3}+2\,BG{R} ^{4}+B{R}^{5}+{G}^{6}+{G}^{5}R\\+2\,{G}^{4}{R}^{2}+2\,{G}^{3}{R}^{3}+2\,{G}^{2}{R }^{4}+G{R}^{5}+{R}^{6},$$ which finally gives $$[R^2G^2B^2] Z(R+G+B) = 6.$$ This generating function includes all distributions of three or fewer colors,e.g. the coefficient of $GR^5$ is one because there is only one way to paint the cube using one color five times and a second one for the remaining face. Note that we had rotations about face pairs, edge pairs and vertex pairs, which is a standard feature in the symmetry groups of regular polyhedra. The reader is invited to compute the cycle index of the symmetry group of the faces of a tetrahedron.

Here is another interesting calculation involving a cycle index.

Best Answer

Related Solutions

[Math] How to find all proper colorings (four coloring) of a graph with a brute force algorithm

[Math] Painting a cube with 3 colors (each used for 2 faces).

Related Question