The Bridges of Konigsberg and Instant Insanity

This was written by our own Michael Cain.

Mike Schilling puts up math posts from time to time, but sticks pretty much to analysis and algebra. Other posts about math education and other STEM stuff appear from time to time but also tend to take a fairly narrow view of what math is. This guest post –hey, I was invited –provides an introduction to graph theory, one of my favorite but lesser-known areas of math, by discussing two problems from the field, one well known and one not so much.

A graph consists of vertices (sometimes called nodes) and edges (sometimes called arcs). When drawn, vertices are represented by circles and edges by lines connecting two vertices (or connecting a vertex to itself). An example of a drawn graph is shown after this paragraph. Graphs may have a variety of properties. In a connected graph, for example, it is possible to follow the edges from node to node and from any starting node reach any other node. The graph below is not connected. While the connected question is obvious by inspection in this small example, answering the same question for a graph with thousands of nodes and tens of thousands of edges can be more challenging. I did my first masters thesis on ways to perform certain operations on big graphs.

Graphs and graph properties are useful in a surprising number of problem fields. The origins of graph theory go back to a paper published by Euler in 1735 (yes, that Euler). The problem is broadly known as “The Bridges of Königsberg.” At the time, the city of Königsberg, in Prussia, spanned the Pregel River and included two large islands. The two shores and the two islands were connected by seven bridges. The bridges of Königsberg problem was to walk through the city and cross each of the seven bridges exactly once. No trickery; just the simple question “Can you do it and how?” A sketch of a failed attempt is shown below: after crossing six bridges, the walkers have no way to reach the seventh bridge without using a bridge they have already crossed. The romantic version of the story had young men and women of a certain age and class using the bridge problem to justify strolling around the city together (with a chaperon trailing behind). In another version, university students attempted the walk with the addition of stopping at a bar for a beer each time a bridge was crossed. Traditionally, such students occasionally announced that they had found a solution, but were unable to reproduce it in the morning after they sobered up.

Euler realized that most of the geography didn’t matter: the problem was independent of the shape of the island or length of the bridges. It could be reduced to a simple graph with vertices representing the land masses and edges representing the bridges. Actually calling it a “graph” lay a hundred and fifty years or so in the future. The transformation from map to simplified graph is shown below. In graph theory terms, the problem is to start from one vertex, follow an edge from the current vertex to an adjoining vertex, repeat, and use each edge exactly once. Such a sequence is now known as an Eulerian path or Euler walk in honor of Euler’s formal posing, and solution, of the problem.

Euler showed that there was no such path in the case of the Königsberg bridges. That much was almost certainly already known – it’s not that big a problem and it only takes an afternoon or so to list all of the possible attempts on paper. Euler is famous for creating a general argument that could be applied broadly. The argument goes as follows. Assume that there is a solution. Then consider any of the vertices except the ones where you start and end the walk (which may be the same). For each of those non-terminal vertices your path must use one edge to reach it, because you didn’t start there, and one edge to leave it, because you aren’t going to finish there. This may happen multiple times, but each trip across always uses two previously-unused edges. So all of the intermediate vertices in a solution must have an even number of edges touching them. In Königsberg, all of the vertices have an odd number of edges. Therefore, no solution can exist. The concept of walks in graphs has been extended in lots of ways since Euler because, well, that’s what theoretical mathematicians do.

So, I can hear everyone: “Yeah, yeah, but you worked in a specialized field, so maybe some of this was professionally useful, but was it ever useful in an everyday situation?” Yes. Back in the 1960s and 70s there was a puzzle on the market called “Instant Insanity”. It consisted of four cubes. Each face of each cube was colored using one of four colors (usually red, green, blue, and white). The goal was to stack the cubes vertically so that each of the four sides of the column showed all four of the colors. As it turns out, the problem can be represented by a graph so that it can be solved quickly and easily (see details below, they’re not important to the anecdote). The graph-theory approach can also be used to show that it’s possible to construct a set of cubes that has no solution. The puzzle company didn’t sell sets like that, but it was possible to assemble one by purchasing two sets and choosing the proper four of the eight cubes.

In my Mom’s office at that time, people would leave little puzzles sitting on a corner of their desk. There was a competition of sorts to see who could solve the largest number of the puzzles that had been set out. One of the men in the office –
call him George, for convenience – was very good at puzzles. George was also obnoxious as hell about how good he was. Mom regularly complained about how obnoxious he was. One year for Christmas I bought two Instant Insanity puzzles and assembled a set for her that had no solution. I told her that there was no solution, but pointed out that George was unlikely to think of that so long as she didn’t tell him. I got regular phone reports for weeks: “George is still trying!” I could hear the smile that went with it. I don’t know if she ever told him that her version of the puzzle couldn’t be solved, but she certainly had a good time watching him struggle. Probably the most-enjoyed gift I ever bought for her.

Instant Insanity Graph Details

The graph-theory solution to the puzzle works like this. First, we build a special graph to represent the cubes, the first graph of the several shown to the left. There are four vertices representing the four colors, labeled appropriately. Each cube has three pairs of “opposite” faces (as you look at the cube, think top-bottom, left-right, front-back to define the pairs). For each such pair of faces, we add an edge to the graph connecting the two colors of the faces in the pair. The edges are labeled to indicate which cube they are from. In this case, cube one has a blue-green pair of opposite faces, a red-white pair of opposite faces, and a red-green pair of opposite faces. If a cube had two pairs of, for example, red-green faces, we would need to add some sort of notation to distinguish between them.

At this point we need some more terminology. A subgraph of a graph is formed by taking subsets of the vertices and edges of the original graph. The second graph in the figure to the left is a subgraph of the first one. The order of a vertex is the number of edge ends that terminate at the vertex. Both ends of an edge that connects a vertex to itself
count in the order for that vertex. In the top graph to the left, the vertices labeled B and G have order five and the vertices labeled R and W have order seven.

Using that terminology, a half solution to the puzzle is a subgraph containing all four nodes and four edges and satisfying two conditions. The subgraph must contain one each of the edges labeled one, two, three and four in the original graph and the order of all vertices in the subgraph must be two. The figure to the left shows four subgraphs that meet those conditions. Using the information from any one such subgraph, we can stack the cubes so that two opposite sides of the column have all four colors.

A full solution to the puzzle exists if and only if there are two half solutions that have no edges in common. In this case it’s easy to see that the second subgraph in combination with any one of the other subgraphs satisfies that condition. A certain amount of flipping and turning of the cubes will be necessary to line things up properly, but those are local movements and the solution is guaranteed to be possible. For this particular set of cubes, there are multiple solutions.

One of the important take-aways from this exercise is that it’s based on a different way of looking at the puzzle information. Graph theory provides a means for manipulating the data so that finding a solution is easy; but the more important thing is that the whole approach is based on thinking about pairs of faces on the cubes rather than about individual faces. By thinking about the problem differently, we still have to search through the possibilities, but the size of the search is dramatically reduced.