# Instant insanity question

My question is regarding the necessary conditions that a graph must fulfill to satisfy instant insanity problem.

Now take for example the left, right, front and back face colors of the four cubes be(the colors are red, black, green and white):

Front   Back    Right    Left
R       W         R       G
G       W         W       B
G       B         G       W
B       R         B       R


Now as you can see on front and back, green and white show up twice respectively which violates the problem. But if we make their graph, their graphs fulfill all the conditions:
1.the graph can be dissociated into two edge disjoint subgraphs
2.each subgraph has vertices of degree 2
3.each subgraph has all the edges representing the four cubes once

Note: I stack the cubes one above the other. This is different from the link i gave in which cubes are kept on the side of each other

-
The cubes have six colored faces, do they not? – Austin Mohr Aug 16 '12 at 17:56
yes....i didn't give the top and bottom colors because i had already found the right graph and these colors could compete for right, left, front and back and as i am stacking the cubes one above the other upper and bottom colors are now not needed – avinash Aug 17 '12 at 11:48

I understand you have to play around with the cubes in order to get the answer. You just know what the fronts and backs; and lefts and rights of each cube are going to be.

"To solve the game, the first graph represents the front and back faces, and the second graph represents the top and bottom faces. Align the cubes according to which edges you have in your two graphs. There is some choice on how to do this; for example, on the game above, cube 1 has the front and back faces blue and green, and the top and bottom faces red and yellow. However, we do not yet know whether blue is on the front or back. You may have to play around a little to arrange your cubes appropriately."

I think all of the cubes are fine the way they are except for the second cube. If you play around with the second cube, then you'll see that if you if you flip it (front becomes back, and back becomes front, but right stays right and left stays left) then you have a valid answer that fits your graph.

EDIT: I think I noticed something. If you think of each of the two graphs as a path, in which you can only walk in one direction, then fill in the answers that way. So you went from R to W, W to G, G to B, and B-R for the blue graph. See how that is one continuous path, and you can fill out your chart in that order. Same thing with the orange graph, even if lines 1 and 2 are not connected. Think of the path as going from red to green to white to black back to red. So you would fill out R to G, then W to B, then G to W, and then B to R in your chart. I don't know if this is actually true, but just a theory.

-

Choosing an orientation of a cube is like picking two edges of the cube, one edge between the left and right vertices and one edge between the front and back vertices. But it also assigns an orientation to each of these edges, because putting red on the front and green on the back is not the same as putting red on the back and green on the front.

You need to assign an orientation to each of the four front-back edges, selecting one vertex to be the front vertex, and one to be the back vertex. Each of the four front vertices must be distinct, and each of the four back vertices must be distinct.

In your picture the edges are symmetric. You should put arrows on them. The arrows on the four front edges can point from the front vertex to the back vertex. Then the edges join up into paths.

Now suppose your choice of edges and arrows is actually a solution to the puzzle. Consider the four front-back edges. Start at one vertex, say Red. There must be precisely one front-back edge that comes out of this vertex, so you can follow it to its corresponding back vertex. Then (unless the new vertex is also Red) you can do it again. You can repeat this until you return to where you started. (This must happen; you never return to any other vertex first.) This defines a simple cycle in the graph. Now if you have not yet visited all four vertices you can pick another vertex to start at, and find another cycle. This will continue until you have a set of between one and four simple cycles that contain all four north-south edges and that together contain each vertex once. Let's call graph that is the union of these cycles “$FB$”.

Now we can do the same thing for the left-right edges, and generate another graph $LR$. Both $FB$ and $LR$ are subgraphs that have four edges each, one from each cube. They are disjoint. And each is a union of disjoint simple cycles.

Finding such $FB$ and $LR$ can often be done just by inspecting the complete graph of 12 edges. Once we have found such, we have a solution to the problem. (In general, for arbitrarily many cubes, it is a hard problem.)

Now let's look again at your graph:

Clearly we can take the red edges to be the $FB$ set and the blue edges to be the $LR$ set. But we also have to assign orientations to the edges, so that the red $FB$ subgraph is made of simple cycles and the same for the blue $LR$ subgraph. For the red subgraph we might assign the orientations so that the path goes from red to green to white to black to red, which corresponds to the partial solution:

  Front  Back
R      G
G      W
W      B
B      R


But your proposed solution has:

  Front   Back
R       W
G       W
G       B
B       R


This doesn't form a cycle, because the $G$ vertex has two edges coming out of it, and the $W$ vertex has two edges coming into it. So it is not in fact a solution to the puzzle.

-