If you love computers – particularly if you love programming computers – then surely, you know the value of grit. You know how important it is to be resilient, to keep going, to forge forward, and convince yourself that there must be a (better) way to do something. But there's another trait that's equally important, if not more important that this: the ability to shift perspective.
Repositioning one's perspective is certainly a hallmark characteristic of a great programmer. All of the developers that I admire and respect exemplify this trait above all others. However, it's not just engineers who have benefited from this – all problem solvers and creative thinkers seem to do this on a daily basis, too. In fact, I'd venture to say that it was their ability to see things with another angle and in a different light that made them the innovators they were.
There is perhaps no better example of this than Leonhard Euler, the mathematician, astronomer, and engineer (justa few of his many titles), who made significant contributions to calculus and the dude who actually created graph theory that we depend on every single day.
But how did he even do this?
Well, for one thing, he definitely didn't do it by waking up one day and thinking: okay you guys, I'm going to make a new branch of mathematics that'll eventually be the cornerstone of how the web works in like, 300 years! Nope. Instead, here's the truth of what happened: he was faced with a simple problem. And the story of how Euler solved this problem centers around how he shifted his perspective, and approached it in a way that no one else ever had before.
Taking a walk through Königsberg
Way back in 1735, Euler heard about an interesting problem that the town of Königsberg was facing.
At the time, Königsberg was a city in Germany, and the city was built around a river called the Pregel River. This city thrived with its merchant economy and part of the reason that it did so well was because it was structured in a particularly interesting way. There were two large islands in the middle of the Pregel River, and they were each connected to one another, as well as to the two riverbanks on either side, which comprised the majority of the city. And how were they connected? By bridges, of course! Seven of them, in fact.
Here's a beautiful print that illustrates the city of Königsberg much better than I ever could:
The citizens of Königsberg spent their Sundays walking around town, enjoying their beautiful city. In the process, they came up with a game – which, as it turned out, proved to be incredibly difficult to accomplish. The goal was to walk across all of the seven bridges crossing the islands only once, without ever repeating a single bridge in the course of one's walk.
At first, when people asked Euler to solve this problem, he brushed it off, thinking that it had nothing to do with mathematics, and therefore wasn't really worth his time. But the more that he thought about it, the more intrigued he became. In a letter to a mathematician friend of his, he wrote:
This question is so banal, but seemed to me worthy of attention in that [neither] geometry, nor algebra, nor even the art of counting was sufficient to solve it.
He was hooked. Euler was so entranced, in fact, that he ended up writing a paper later that year that would contain a solution to the bridge problem. But before we understand how Euler solved this problem, we need to cover a few basic graph theory rules first.
Degrees and paths and cycles, oh my!
We've already learned about some of the different types of graphs that are possible through graph theory, like directed and undirected graphs. But, we've still only just scratched the surface of how graphs work.
For example, just as edges can be classified as directed or undirected, vertices (or nodes, as they're sometimes called) can also be categorized based upon how they link to other nodes in a graph.
Let's take a look at the graph to the side.
From first glance, we can already glean a lot from this seemingly simple structure. We know that vertex C is connected to vertex D. And we also can tell that vertex B is not connected to vertex D. Easy, right?
Well, these connections end up being important as a graph grows, and it can be helpful to be able to easily identify which vertices are connected with other vertices. The term we use to describe two connected vertices is adjacent. For example, vertex F and E are adjacent because they have a common edge (the edge FE connects them).
Another useful (and important!) way of classifying vertices is by their degree. The degree of a vertex is the total number of vertices that are adjacent to that vertex.
The tl;dr version of defining the degree of a vertex: how many neighbor vertices does this node have?
Vertex D is only connected to one other node, so it has a degree of 1. Vertex C, on the other hand, has four other neighboring nodes, which means that it has a degree of 4. Important thing to note: a vertex could have an even or an odd degree – but we'll dive into that more a bit later.
Okay, so we can classify edges based on whether they are directed or undirected. We can also classify vertices based on how many other vertices they are connected to.
Cool.
But wait: there's more! (Obviously). There's yet another way to identify graphs, and it has to do with how we traverse through a graph – that is to say, the way that we get from one vertex to another.
Generally, when we use graphs to implement a data structure, we're concerned with how our data relates to one another. Which is to say, we care about how nodes are connected to other nodes because we usually want to get from one node to another. This is where graph traversal comes in. There are different algorithms that can come in handy for traversal, depending upon what type of graph you have. But we won't get into those today. Instead, let's start simple and talk about the words that we use when we talk about walking through a graph.
Most of the time, when people refer to traversing through a graph, they use the term “path”. A path in a graph just means the way that you can get from one vertex (the origin) to another (the destination). In order to get from one vertex to another, we have to traverse through some edges in the graph.
A path represents which node we're starting from, which edges we're passing through, and which node we're ending at.
However, many times people mix up the term “path” with the term “simple path”. They're actually a little bit different, and it's important to acknowledge what sets the two terms apart. A path doesn't have to follow any rules – we can start wherever you like and traverse through the graph in whichever way we'd like, just as long as we end up at the destination node. Simple paths have a lot more rules that must be followed.
A simple path is a unique type of path that is far more constricted: in a simple path, no nodes or edges can be repeated while traversing the graph.
If you ever find yourself in front of a graph problem, be sure to clarify and understand if you are dealing with finding a path through the graph, or a simple path – because they can profoundly impact the way that you deal with the data structure.
Finally, there's also the cycle, which is a simple path, except that we must end our traversal at the same node that we started off at. That is to say, the starting “origin” node is the exact same as the ending “destination” node, and we have traversed all the nodes and edges of the graph in the process.
We already know that the formal definition for a graph is an ordered pair, containing a set of vertices and a set of edges. We can define a path (or a simple path, or a cycle) in a similar way: as an ordered list of directed edges. The directed edges here is important since we need to be able to show which node is the origin, which node is the destination, and which edge we're traversing as we cross from one node to another.
Okay, okay–we've covered all these terms and rules and stuff, but what I want to know is…what happened to Euler?! Well, it's time to (finally) find out.
Walking the Eulerian path
When Euler was solving his seven bridge problem, he broke it down into smaller, bite-sized pieces. He simplified the problem into parts, and visualized the bridges of Königsberg in a different way.
Ultimately, he solved this problem by approaching it with a different perspective. Instead of writing out every single possible path crossing (which Euler noted would be unsustainable/unscalable, and inefficient), he simplified the problem by visualizing it. In his notebooks, which we are lucky to have preserved and still have today, Euler drew out the bridge problem to look something like this:
According to analysis of Euler's notebooks conducted by the Mathematical Association of America, Euler represented the landmasses as capital letters – A, B, C, D – and decided to track a bridge “crossing” by the landmasses that one started at and ended at. For example, to cross from landmass A to B, the trip on the bridge would be referred to as AB. And if one were to then cross from landmass B to D, the entire journey would be visualized as: ABD. This would represent crossing two bridges, and touching three landmasses.
In the process of doing this exercise, Euler realized that in order to cross seven bridges – as was the case in the city of Königsberg – the problem needed at least eight “landmasses”, or letter sequences in order to solve the problem.
Euler realized that it was impossible to cross each of the seven bridges of Königsberg only once!
The way that Euler solved this problem was by changing his approach, and creating a kind of representation that no one had really done before. He visualized the seven bridges problem as a network, which eventually became the basis for the graph structure that we know today. Centuries after Euler solved this problem, mathematicians redrew his same representations in graph format, which should look very familiar to us:
Even though Euler solved the puzzle and proved that the walk through Königsberg wasn't possible, he wasn't entirely satisfied. So he kept going and found that, given certain situations, it is completely possible to cross the bridges of “network” only once.
Today, we often refer to this type of graph traversal as a graph with a Eulerianpath or with a Eulerian circuit.
A Eulerian path is a path wherein we only visit each edge in the graph once, while a Eulerian circuit is a Eulerian path that is a cycle – we only visit every edge once, and we end on the exact same node that we started off on.
Euler determined that, given a certain set of circumstances in a graph/network, a simple path can be possible to find. And because of him, we have yet another way to classify graphs: based on whether they are Eulerian or not.
Euler's mathematical proof determined that there are certain conditions that a graph must meet if we are to traverse through its edges only once.
For example, in order for an undirected graph to have a Eulerian cycle, all of the vertices with a degree in the graph must be connected – that is to say, all of the vertices that are connected in the graph must have a degree greater than zero – andall of the vertices in the graph must be of an even degree.
Similarly, in order for an undirected graph to have a Eulerian path (but not a cycle), all of the vertices with a non-zero degree must be connected, and one of these two things must happen: 1) two vertices must have an odd degree OR 2) all of the vertices in the connected graph must be of an even degree.
This can be a little bit confusing unless we really stop and think about it. I love the way that professors of The NRICH Project at the University of Cambridge explain why this bridge problem isn't possible based on Euler's proof:
Euler proved it couldn't be done because he worked out that to have an odd vertex you would have to begin or end the trip at that vertex. (Think about it). Since there can only be one beginning and one end, there can only be two odd vertices if you're going to be able to trace over each arc only once. Since the bridge problem has 4 odd vertices, it just isn't possible to do!
Ultimately, it all came down to the degrees of the vertices in the end! (Remember I said that was going to be important?) It isn't possible to solve the bridge problem if there are four vertices with an odd degree.
According to Euler's proof, we could only solve it if either all the vertices in the graph were even, or if only two of the vertices were odd. But four odd vertices? Nope. No way.
In the graphs below left, you'll notice some situations where Euler's proof holds up to the test.
In Graph 1, there are two vertices (A and E) with an odd degree, and so it is possible to traverse each edge once. However, we won't end up at the same vertex that we started on.
In Graph 2, all of the vertices have an even degree, so we could not just traverse each edge only once, but we could end up at the same place that we started!
Graph 3 though – sadly, there's just no possible way to make this work on a Eulerian level. This graph has the exact same issue as the Königsberg problem: there are four vertices that are odd, and since we know we can never have more than two odd degree vertices, we can be sure that this graph isn't Eulerian, in the slightest!
What happened to Königsberg – and its bridges?
The story of what happened to Königsberg after Euler put it on the map is interesting (and also a little bit sad!). In 1875, the city built another bridge between the nodes B and C. This resulted in only two vertices with an odd degree, which solved the impossible walking problem!
But, unfortunately, in the case of Königsberg, all did not end that well. When Prussia dissolved, Königsberg eventually became a part of Russia. Two of the original bridges were bombed by Allies in 1942, during WWII. Two other bridges were later demolished to make room for a highway. And, the city has since been renamed Kaliningrad.
You can still visit Kaliningrad today, and walk your own Eulerian path across the five bridges that remain. Because, guess what – now, it's possible! I like to think that Euler would probably get a good laugh out of that.
Resources
There is a copious amount of research and writing around Euler's approach to the Seven Bridges problem. I couldn't get into the details of all of it, but the details are out there! If you want to cross all seven bridges on your own, I suggest starting with this handy resources.
- Early Writings on Graph Theory: Euler Circuits and The Königsberg Bridge Problem, Professor Janet Heine Barnett
- Eulerian Path and Circuit for Undirected Graph, GeeksForGeeks
- The Seven Bridges of Königsberg, Professor Jeremy Martin
- Leonard Eulers Solution to the Königsberg Bridge Problem, Teo Paoletti
- Graph Theory, WebWhompers
Top comments (2)
Something is bothering me with the maths of the remaining bridges at the end.
There's 7 bridges in the beginning
Okay
The city builds one more to solve the problem
That makes 8 bridges
2 were bombed
2 were demolished
That leaves us with 4 bridges
But you say there's 5 remaining ?
Thanks for the article! Great and clear as always :)
A small history fact check though, if I may. The city of Königsberg did not become Kaliningrad with the collapse of Prussia (or rather German Empire), but only after the end of the World War 2.
The entire German population either left with the retreating German troops or was later deported by the Soviets, and so the region became part of Soviet Russia and was eventually completely Russified.