Graph Theory Applications – The Instant Insanity Puzzle

Extracting Sub graphs through Eliminations

Here is a step by step diagrammatic elimination for the solution

Step 1: Remove the self loop

 

step01

Step 2: Identify a vertex with degree four, such that it can contribute as vertex of degree two in both the sub graphs (clearly it is the green one). IN each sub graph choose one of the edges (the edges must not repeat in both the sub graphs)

We retain edge(3) between (G,W) in the first sub-graph and we are left with edge (2) in the second sub graph.

step2

Step 3:In the first sub graph we can eliminate all other edges with label 3 as we have already chosen the edge (W,G) with label 3. Similarly in the second sub graph, we already have edge(2) from (W,G), hence, we can eliminate all other edges with label 2.

step3

Step 4: In the first sub graph, edge (4) between (R, B) has to be retained as that is the only edge between these two vertices, hence eliminate all other edges with the label 4. Similarly in second sub graph retain edge (1) between (G, R) and eliminate all other edges with label 1.

step4

Step 5: As we know that the same edge cannot appear in both the sub graphs, we can eliminate the edge (1) between (G, R) from the first sub graph as it is must be a part of the second sub graph. Similarly, the edge (4) between (R, B) in second sub graph can be eliminated.

step5

Step 6: In the first sub graph, we can eliminate the edge (2) between (W,B) because 2 already exist between (G, R). In second sub graph, the edge (3) between (W,R) will make the degrees of both the vertices as 3 which is not desirable as per our restrictions. Hence, we delete the edge (R, W) to get the following graphs:

step6

And this is the desired solution.

What does this solution means?

The first sub graphs demonstrate that if the four cubes are stacked one above the other, it will look like the following:

  1. The first cube will have front colored blue and back as white.
  2. The second cube will have green in the front and red at the back.
  3. The third cube will have white in the front and green at the back.
  4. The fourth cube will have red in the front and blue at the back.

The second sub graph  demonstrates that

  1. The first cube will have red in the left and green in the right.
  2. The second cube will have green in the left and white in the right.
  3. The third cube will have blue in the left and red in the right.
  4. The fourth cube will have white in the left and blue in the right

And this matches our solution on the first page. 🙂

Summary

This is an awesome puzzle and is very good to demonstrate that graph theory can make such puzzle look so easy. The power of graph theory lies in its simplicity.

Note: The final sub graphs are also called edge disjoint sub graphs as no edges are common in both the sub graphs.
Please let me know in comments, in case you few things were not clearly. For more details on the topic you can try looking at the WIKIPEDIA