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?
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.