# 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.

It’s been a while since I’ve had cause to use one as a data structure, but graphs are common in computer science specifically because they lend themselves well to searching & sorting algorithms.Report

Actually, almost anything in CompSci can be mapped over to graphs. For example, integer programming programs are typically presented in linear algebra form. However, if they fit certain (not uncommon) constraints, they can be represented as network flow problems (over a graph), which then allow for more efficient solutions. Doing such things is literally routine. In fact, I seldom dig too deeply into a problem before I try to turn it into a graph.Report

Of course it cuts both ways. Google’s original

Page Rankproblem looks at first like a graph problem, but it is solved as an eigenvector problem. Cuz math is awesome!ReportPathing too, and emergent behavior.Report

Which is kinda how I used them in my masters thesis, to navigate an unstructured mesh.Report

@michael-cain, I’m not sure this is the sort of post that gains a lot of comments, but I thought I’d let you know that I enjoyed reading it. You got me to exercise a part of my brain that doesn’t often get to come out and play.Report

It was possible to doctor a Rubik’s cube to make it unsolvable by carefully prying out a corner piece, rotating it, and putting it back in place.Report

Similarly, IIRC, if you start with an empty Sudoku grid and just randomly fill in some spaces to make a plausible puzzle, i.e., no obvious repeats in any row, column, or block, there’s exactly fifty percent chance that it’s solvable.

I seem to remember the same sort of thing applying to a Rubik’s cube.Report

Rubik cubes have three kinds of parity:

If you exchange any two pieces, it becomes insolvable. If then you exchange any two pieces a second time, it becomes solvable again.

If you flip any edge piece it becomes insolvable. If then you flip any edge piece a second time, it becomes solvable again.

If you rotate any corner piece it becomes insolvable. To make it solvable again, you need to flip a corner piece in the opposite direction, or flip two corner pieces in the same direction.

So, if you take it completely apart and put it back together at random, there’s a 1/12 chance the result can be solved.Report

When I took it apart, I always put it back together solved. 🙂Report

Ah, the elusive human factor.Report

You’ve given me something to ponder that will drive me to distraction until I understand exactly

whythis works like this. Thanks a lot, Obama!ReportJust don’t try to work out the proofs using your truck and bridges on your route. That’ll waste a lot of gas.Report

If elected Mayor of Konigsberg, I will make my number one priority the building of an eighth bridge!Report

IIRC, Königsberg’s bridges didn’t all survive WWII bombings, they only have five now, and an Euler walk is possible. Bummer for the students: “Dammit, Franz, now that you’ve solved the puzzle we’ll have to find another excuse to wander around drinking!”Report

If you get really stuck, you can always post questions in a comment, or I think if you follow my gravatar there’s an e-mail address that gets checked regularly.Report

I just have to say that using the term “graph” to describe what you describe above when it has a much more commonly known/understood definition within the discipline of math is… confusing.

I recognize you are using the terms properly. It’s just strange that the terms exist as they do.Report

Actually, the graph you are thinking of can fit into the definition of what Michael is talking about.Report

Wait till we bring up lattices.Report

This is a field.

These are also fields.

Report

Report

Report

If at first you don’t succeed, try, try again. Then quit. There’s no point in being a damn fool about it.Report

This is a field, too:

+ 0 1

0 0 1

1 1 0

* 0 1

0 0 0

1 0 1

Since in any field 0 != 1, it’s the smallest one.Report

I think you’re all outstanding in your fields.Report

None of which has anything to do with R and C!Report

Now there’s a math history question I’ll have to look into some day: did a “graph” of a function as the term is commonly used today come into use before or after “graph” in the vertices/edges sense?Report

Euler was one of the titans of mathematics. (Yes, that is a pun.)Report

That was back when he lived in Houston.Report

In my design work, I do a lot of graphing. Maybe it’s the stitch-twistings for a complicated Aran sweater, with all it’s ropes and honeycombs, or charting a lace pattern or colors patterns for a Fair Isle sweater or teddy bear design on a kid’s sweater.

But that’s basically all flat (or a cylinder), and knitting is 3-d (or else your socks wouldn’t have heels, socks didn’t used to have heels, in fact, the heel was a giant innovation in the craft). I often make sculptures, things knit freeform to resemble a horse, a flower, a leaf, etc. It’s easy to do, I comprehend how to get the shapes I want, and I have strong three-dimensional perception, for a girl in particular. (Seriously, army tried hard to recruit me, they told me all about it at length on multiple occasions).

The problem is, it’s difficult to 2-D charts for 3-D objects.

Until this came along (and chart hounds, please take a look.)

http://stitch-maps.com/

You can’t imagine how this very-recent innovation twitterpated the knitting world.Report

Somewhat relatedly, one of the graph theory problems that goes back a long time is deciding whether a particular (usually large) graph can be drawn on a plane without any of the edges crossing. Eg, the very first figure in the post is drawn with two edges crossing, but could be redrawn so that they don’t cross. This problem, and algorithms for finding how to draw the graph, got a

lotof attention when the wiring for integrated circuits and printed circuit boards began to get seriously complicated.ReportThere’s a game app based on that idea you might enjoy called “Flow [Free]”. My ten-year old loves it. Who woulda guessed she was a natural at graph theory? 😉Report

I believe it. And I’m not surprised that it’s its own science, either.

What intrigues me about the charting system I linked to was who uses it: often people who have little math background, and little more then rudimentary design skills; but this charting system is so representative of the work they’re producing that it’s almost intuitively understandable; the biggest challenge is coming up with a marking system to keep your place as you work through it. That’s a pretty impressive step forward in charts and graphs for everyday use of an ancient craft.

The system it replaces (still the norm) uses a straight grid with grayed-out areas for places where there are ‘no stitches,’ allowing for 3-D patterns to grow rather like a flattened-out orange peel or map of the globe, but also very confusing for people who don’t get that flattening produces gaps in the 2-D representation.Report

Interesting post @michael-cain

Graph Theory isn’t something I do much (there’s not much call for it in economics), but it did come in handy for one of the puzzles in Dragon Age: Inquisition.Report