4
$\begingroup$

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:

  1. W R Y W
  2. Y R G W
  3. 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.

$\endgroup$
  • 3
    $\begingroup$ You may find an answer if you search for "instant insanity", maybe even better if you include "graph theory" in your search. If you find something good, write up a summary of what you find, and post it as an answer. $\endgroup$ – Gerry Myerson Dec 8 '14 at 8:18
  • $\begingroup$ For each cube, you need a graph that shows the relationships between the colors, not the sides. $\endgroup$ – Nick Dec 8 '14 at 19:26
1
$\begingroup$

This paper (web archive) explains everything nicely.

In the nutshell:

  1. Draw a graph consisting of four disconnected vertices R, G, Y, and W.
  2. 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):

  1. R - 3 - W - 2 - G - 1 - Y - 4 - R.
  2. 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.