[MUSIC PLAYING] Imagine you have four cubes whose faces are colored red, blue, yellow, and green, as shown.

Can you stack these cubes so that each color appears exactly once on each of the four sides of the stack?

[MUSIC PLAYING] Here are the four cubes again labeled 1, 2, 3, and 4.

Now, the coloring on these cubes is very important.

In other words, we're only considering these four particular cubes.

So for example, cube number 1 has exactly three red faces and one yellow, green, and blue face.

Moreover, those colors appear on the particular faces as indicated, and similarly for the other cubes.

If you just happen to have four cubes with this exact coloring, I encourage you to go get them and try to figure out the answer, or pause the video and check out the link in the description below.

There, I've included a template of the cubes, which you can print off, cut out, and tape together to make your own.

All right, there are thousands of different configurations that we can make with these cubes, 82,944 to be exact, which is why this is often called the Instant Insanity puzzle.

So out of these thousands of possibilities is there one that works?

That is, is it possible to stack the cubes so that each color appears exactly once in the front, back, left, and right sides of the stack?

Today, we'll attack this puzzle using math with no numbers.

In particular, the mathematics of graph theory, the study of graphs.

Kelsey's done a few episodes featuring graphs, but we'll just recap the basics.

A graph is just a collection of vertices and edges like these.

You can have things like multiple edges between vertices or loops, an edge from a vertex to itself, or lonely vertices with no edges.

And here's some terminology.

If you start with a graph and then delete vertices or edges, the result is called a subgraph of the original graph.

And if you decorate your edges with arrows like this, then the graph is called a directed graph.

And this is all we need to know to solve the puzzle.

How so?

We can drastically simplify the puzzle by encoding the information of each cube with a graph.

For example, here's the first cube.

To represent it with a graph, let's draw one vertex for each color and draw an edge between two vertices if those colors are opposite faces on the cube.

Now, notice that the positions of the faces aren't fixed because we can rotate the cube.

For example, here, yellow is on bottom and blue is on top.

But we can rotate it so that blue is on bottom and yellow is on top.

To help keep track of this, let's use a directed graph to indicate a particular orientation.

Let's say that arrows point from left to right, from bottom to top, and from back to front.

So when our cube is sitting like this, its graph looks like this.

And if you want to rotate the cube, just swap the direction of one or more edges.

Now, already you can see there some ambiguity, like if we rotate another way, then blue and yellow can appear on the left and right sides, so how do we account for that in the graph?

It's actually pretty easy to handle, and we'll take care of it later on.

By the way, I've labeled each edge with a 1 just to remind us that this graph belongs to cube number 1.

Doing this for the other three cubes, we get the following graphs.

They're undirected for now, but we'll throw in some arrows later.

But now is a good time to pause the video just to make sure it all makes sense.

All right, we've encoded information about each individual cube with a graph, and now we can use this to capture information about the full stack.

How?

Simply superimpose the graphs to form a new graph, which I'll call G. This contains all of the information of the full stack, except it's too much information.

Just like Michelangelo chipped away at the marble to reveal David inside, we also need to delete, or chip away at, some of the edges to reveal the solution to the puzzle.

So here's the plan.

To solve the puzzle, let's find two subgraphs of the graph G. I'll call them A and B.

A will represent the front and back faces of the stack, while B will represent the left and right faces.

But how do we know what and B should be?

Well, let's just think about the front and back faces of the stack, subgraph A for now.

We want all four colors to appear, right?

That means the subgraph should have exactly four vertices, so nothing like this.

And the same is true for the second subgraph.

We want all four colors to appear on the left and right faces of the stack, so A and B should have exactly four vertices.

OK, great.

So here are two subgraphs with four vertices.

And I've arbitrarily directed the edges.

Does this count as a solution?

Well, A tells us to stack cube number 1 so that its front face is green and back face is red.

And cube number 2 with yellow in front and read in back.

The third cube with red in front and blue in the back.

And the fourth cube, well, we don't know.

A doesn't contain an edge labeled 4, so we don't have enough information.

This suggests that each subgraph should contain edges from all four cubes.

That is, the edges should be labeled by all four numbers-- 1, 2, 3, and 4.

That is condition number two.

So we need a different subgraph for A, and we'll come back to it.

But what about B?

B satisfies condition number two, so could this be a solution for the left and right faces of the stack?

Well, no.

Why?

B tells us to stack cube number 1 with green on the right and red on the left.

But it also tells us to stack cube number 1 with blue on the right and yellow on the left, but we can't have both.

The problem is that subgraph B contains two edges labeled with 1.

It also has two edges labeled with 2, so we face a similar problem for cube number 2.

So what's the fix?

Not only must each subgraph contain edges labeled by all four numbers.

Each number must occur exactly once.

Just to recap, to find the solution to the puzzle, we need to subgraphs-- A and B-- so that, number one, both subgraphs contain all four vertices, and number two, the edges of each subgraph must be labeled by all four numbers-- 1, 2, 3, and 4, exactly once.

And is that it?

Well, take a look at this graph.

It satisfies the previous two conditions, but it's also problematic.

Notice that blue appears twice on the back.

The reason is because the blue vertex has two edges directed away from it.

And here's another problem.

Neither red nor blue appear on the front.

That's because neither the red nor the blue vertex has an edge directed towards it.

These are both things we want to avoid.

So to get around these problems, here is condition number three.

In both subgraphs, each vertex must have exactly two edges incident to it, or sticking out of it.

Moreover, one of those edges should be directed in to guarantee that that color appears on the front and right, and the other edge should directed out to guarantee that that color appears on the back and left.

And OK, this seems like it should solve the puzzle.

But before we get too excited, let me just point out one last condition.

Whatever the correct subgraphs are, we don't want them to have any edges in common.

For example, if both A and B have this edge labeled 1, then we'd need to stack cube number one so that green faces the front and red faces the back while simultaneously having green face the right and red face the left.

But that's nonsense, because you'd need two copies of cube number 1.

So let's add condition number four.

The subgraphs should not have any edges in common.

All right, I claim that does the trick.

All we need to do is pick out two subgraphs of the graph that satisfy these four conditions, and we solve the puzzle.

Now, I strongly encourage you to pause the video and see if you can find the graphs, because I'm about to reveal the solution.

Ready?

Here it is in three, two, one.

Voila.

If we stack the cubes like this, then all four colors appear on each of the four sides of the stack.

See how cool graph theory is?

To close out, I'll leave you with two questions to think about.

First, we found one solution, but is it the only solution?

Another question.

Here's a set of four different cubes.

Can you use graph theory to find a solution to the Instant Insanity puzzle with these cubes?

Let me know what you come up with in the comments.

Have fun, and see you next time.