# Vertex coloring

Disclaimer: I'm not a mathematican. Please answer in a way a non-mathematican can understand. Thank you.

I'm building kind of a wooden puzzle and got stuck. My problem is: I have squares whose 4 edges have x different key-and-slot-patterns. Each square looks the same. Now I can join different squares to each other (edge-to-edge) as long as the edges don't share the same key-and-slot-pattern. I prefer to see the keys and slots as a "color". That way each square has x colors whose edges can be joined to each other as long as their color differentiates. Joining may happen planar or perpendicular. In a first step I want to build a cube whose 6 faces consist out of 6 squares. I want to know how many different edge colors I need when building a) an ordinary cube b) a cube in cube system like the rubic's cube (3x3x3). Can anybody give me a tipp where to start?

Here's a picture of the "keys-and-slots" and the resulting cube:

-
Please consider that the squares (tiles) can be flipped which results in a mirrored "key-and-slot-pattern". They also can be rotated. – prinzdezibel Jan 7 '12 at 14:21
I thought I understood what you're saying but the sentence "That way each square has $x$ colors whose edges can be joined to each other as long as their color differentiates." threw me off. It seems to refer to colors of edges of colors. Did you mean "That way each square has $x$ colors and the edges of the squares can be joined to each other as long as their color differs"? Also, how should we interpret "I have squares whose $4$ edges have $x$ different key-and-slot-patterns." and "each square has $x$ colors"? Is it the edges or the squares that have $x$ colours each? – joriki Jan 7 '12 at 14:38
I think you'll also need to say more about the flipping and rotating. If I flip a square and get a mirror image of its key/slot pattern, will that correspond to one of the other patterns? Also, if the squares can be joined perpendicularly and their patterns can be rotated and flipped, how do you decide which of them differ? This no longer seems to gel with the colour paradigm. – joriki Jan 7 '12 at 14:43

Independent of whether this particular scheme of colouring the squares works, $2$ colours will always suffice, since you can take each edge in the finished cube and colour the two edges that will be forming it differently. – joriki Jan 7 '12 at 15:27
@prinzdezibel: Yes, that was clear enough. If you put your cube together (without nozzles at first) and for each cube edge mark one of the square edges forming it "$1$" and the other one "$2$", then take the cube apart, then put $1$ nozzle in the middle of every square edge marked "$1$" and two nozzles to both sides of the middle of every square edge marked "$2$" and then put the cube back together, everything will fit, and you've only used two different patterns a.k.a. colours. – joriki Jan 7 '12 at 18:28