## Applications of Graph Theory

Graph Theory is used in modelling and solving a lot of real world problems, games and puzzles. Here we discuss a very famous puzzle ” The Instant Insanity ” problem.

The goal of this post is to demonstrate that such complicated problem statements can be so easily modeled and solved using Graph Theory. Also I would like to build some more interest into Graph Theory. If you want to feel more comfortable with the basics of Graph Theory, here is a list of primers you might like to read once.

## Problem Definition – The Instant Insanity Puzzle

There are four cubes such that the six faces of each cube is variously colored with either of the four colors (BLUE, GREEN, RED and WHITE). The distribution of colors on each cube is unique.

The objective of the puzzle is to stack these cubes in a column so that each side (front, back, left, and right) of the stack shows each of the four colors.

## Solution

An exhaustive search for a possible solution would be almost impossible. If we still try to systematically test all possible arrangements, we will end up having 3 * 24 * 24 * 24 = 41472 unique cases to be tested.

Hence, we need to find a better approach to this and almost all such puzzles can be solved using some knowledge from the graph theory. Considering the above cubes we have to understand the following:

If the cubes are stacked one above the other, no two faces on one side must have the same color. And there are four such sides to it. Let us name the sides as LEFT, RIGHT, FRONT and BACK.

Here is the solution to the cubes showed above:

I will try to solve this in a way where you are not expected to have any knowledge of graph theory except for the fact that a graph has vertices connected with by edges.

**Steps to solution**

- Let us draw a graph with four vertices, each representing one of the colors.
- Let there be an edge between two vertices (v1 and v2) if the opposite faces of the cube have colors represented by v1 and v2.

Here is the image of the four cubes just for convenience:

We will name the vertices as R, G, W and B. The edges will be named as 1, 2, 3 and 4 depending on which cube they come from.

Keeping these two points in mind, we will have the following:

- Three edges labeled (1) can be drawn between vertices {B,W}, {R, R}, {G, R}. These edges come from the first cube.
- Similarly three edges labeled (2) can be drawn between vertices {W, G}, {G, R}, {W, B}. These edges come from the second cube.
- Similarly three edges labeled (3) can be drawn between vertices {R, W}, {B, R}, {W, G}. These edges come from the third cube.
- Similarly three edges labeled (4) can be drawn between vertices {W, B}, {G, G}, {R, B}. These edges come from the fourth cube.

Below is the corresponding graph:

This was the toughest part of the solution. Now it is just simple extractions. Let us break down the problem and solve it in pieces. As per the expected solution, we need 16 faces or two sets of eight opposite faces (front-back) and (left-right) of the four cubes.

Also, consider one set (left-right) i.e. eight opposite faces at once. Which means, we can probably think of it as one sub graph of this graph. Similarly the (front-back) can be represented by another sub graph.

** What should be the restrictions on these sub graph?**

- Both these sub graph cannot have the same edge. This is because an edge represent the opposite faces of a cube in left-right or front-back arrangement. And, hence the same pair cannot be present in both the arrangements.
- These sub graphs must have only four edges. This is because we are only concerned one pair of face from each cube.
- Each vertex of the sub graph must have degree 2. This is because, a degree two means that a vertex or color can be used at max in two cubes (one at the front face and other at the back) If it has a degree more than two, then there is a possibility of a particular color being repeated on either of the sides.

With these restrictions, it is very clear that we cannot have the self loops in any of the sub graphs because the moment we have one self loop it will force one color to be repeated more than once on one of the sides.

After removal of the self loops, if there are only two edges incident on any vertices, those two edges will be retained in either of the sub graphs. And rest all can be done through eliminations: