Set theory is, alas, going to need to take a break. I left my books on the train on friday. $200 worth of textbooks down the tubes, unless one of the conductors happened to hang on to them. At least I’ve got a pre-order already placed for a copy of the new addition of Ferreirós book; between that, and a new copy of Quine, I should be OK. But in the meantime, we’ll look at something else. Since I mentioned graph theory on friday, and I’ve been promising forever to write about it, I figured this is a good time.
My favorite introduction to graph theory is stolen from one of my grad school professors. It’s the first major use of what became graph theory, which is a proof by Euler.
Here’s the problem. Back in the 18th century, Euler lived in the city of Königsberg in Prussia. Königsberg is a city built around a fork in a river: it’s got parts of the city on the banks of the river, and parts on two islands. To get around
the city, there were seven bridges connecting the parts of the city. Is it possible to
take a trip through the city of Königsberg, crossing each bridge exactly once? More generally, given a city like Königsberg, how can you figure out whether it’s possible to tour the city crossing each bridge exactly once?
Over to the right is a schematic map of Königsberg when Euler lived there. For Königsberg, you can show that it’s impossible, by exhaustively listing all paths. It’s a lot of possible paths, but not so many as to make it effectively impossible. But there’s a better way of figuring it out. It’s a property of the
structure of the city and how the graphs connect different parts of the city. And that’s the key to the problem: analyzing the structure. And the structure is a graph.
For this problem, you can look at the city as a simple structure. Each land-mass – the two banks, and the two islands – can be viewed as points (vertices). Each of the bridges are lines (edges) connecting the points – like in the image to the right. The question becomes: given a collection of vertices connected by edges, when is it possible to cross every edge exactly once? If there’s a way to do it, then the path is called an Eulerian path. If there’s a way to do it so that the Eulerian path ends at the same vertex as where it started, then the path is called an Eulerian cycle, and the graph is called an Eulerian graph.
The answer to this problem is, as I said, in the structure of the graph.
If we want an Eulerian path, then we can easily show that there is an
Eulerian cycle if and only if the graph has the property that you can partition its edges into a collection of disjoint loops (cycles). Look at the graph of Königsberg above: you can form cycles with 1/3 and 2/4, or 3/5/6 and 2/4, or 1/2/7/6, or… But you can’t partition all of the edges into disjoint cycles.
Studying graph structure using some combinatoric techniques, you can show the more general result about Eulerian paths: if every vertex in the graph has an even number of edges, or it has exactly two vertices with an odd number of edges, then
the graph has an Eulerian path. Again, look at the example: there are three nodes with 3 edges, and one node with 5 edges. So there are 4 nodes with odd numbers of edges. Therefore, there is no way to make an Eulerian path through Königsberg.
How many bridges would you need to add to make a graph with an Eulerian path? You need to make two of the four nodes have even numbers of edges. We can do that by adding one edge. For example, if you add an edge from A to D, then you have one node with 5 edges, one with three edges, and two with four edges.
Edits: “My favorite introduction to set theory” in the second paragraph, “eulerian path” in the fifth, “Bridges” in the last.
The thing I love about the proof for eulerian paths is how intuitive it is: If you’re drawing a path, every node you pass through obviously has to either have an even number of edges (since each time you enter it, you have to exit it), or have an odd number and be the beginning or the end of your path, since those are the only nodes that you enter without exiting, or vice-versa. As a special case, your start and end nodes might be the same, in which case you have no nodes with odd edges.
It’s one of those beautiful proofs where the result seems non-obvious until you point out the obvious things that make it so. 🙂
Slight nitpick on the history: I don’t think Euler ever lived in Konigsberg. When he solved the problem in 1736, it was remarked upon that he’d never even visited the city. At that time Euler was head of the mathematics department at the Academy of St Petersburg.
I hope you didn’t lose a copy of Kunen (Introdution to Independence Proofs) . While a classic, that sucker is out of print.
isn’t that what eBay is for? you just know some other sucker’s gonna have a copy hanging around. the kind that’ll look at it every now and again, scratch her head and think, Wonder why this old dude thinks we have to PROVE independence. Where are we, the British Empire? Pfeh.
Lepht
(does have some faith in humanity left… somewhere)
There a nice picture superimposed on the historical view of Königsberg:
http://upload.wikimedia.org/wikipedia/commons/5/5d/Konigsberg_bridges.png
It is used in a nice (German-language) e-learning unit on the topic: http://www.matheprisma.uni-wuppertal.de/Module/Koenigsb/
I cannot find a reference either to Euler being in Königsberg or not, but since he was in Berlin and in St. Petersburg, and since Königsberg (on the Kurische Haff) was an extremely popular “wellness spa”, as we would say today, it is quite possible that he visten on his way to St. Petersburg.
This is the kind of question you need real science to answer and not just Google 🙂
Can’t wait till you get to Bipartite Graphs, my favorite!
When I tried to learn Decision-Maths which was an awful lot of graph theory, I failed, twice, mostly because it was a lot of memorising algorithms which was far too boring. I couldn’t be bothered to memorise anything and I didn’t really appreciate what was going on behind it, actually I still don’t but hopefully I will next time I learn this stuff.
Nice simple explanations like this are much better.
Walker:
Nope, didn’t have Walker. My two texts were the Quine, and (I think) Stoll. The Quine is the one that I’ll miss; overall, it’s not the clearest text in the world, and the typesetting is a monstrosity, but parts of it are wonderful.
Actually, if you add a bridge between any of the landmasses, you can make an Eulerian path.
I have checked several sources all of which say that the Königsberg Bridge Problem was a well known problem that Euler heard of and solved whilst living in Sankt Petersburg. As WiseWoman says this does not exclude the possibility that he visited Sankt Peterburg at some point in his life but he certainly never lived there. I personally do not think Saint Onan was nitpicking as I believe that the history of science/mathematics should be handled with the same seriousness and accuracy as science or mathematics themselves and not with the sloppiness that is all too oft unfortunately the case.
Konigzberg did have one very important citizen in the 18th century, the great philosopher Emannuel Kant. Kant was born in 1724, so he was 10 years old when Euler solved the problem. Kant became a professor at the University of Konigsberg – famously, he never left Konigsberg ever, but his philosophical writings (on knowledge & ethics, mostly) made him famous. According to legend, he took his professorial walks at the same time every day so that his neighbours set their clocks by his apprearance. No doubt he often walked over the bridges of the problem.
PS The legend adds that Knat failed to appear one day at the usual time so that his friends went to see if something was amiss. They found him immersed in a book by Rousseau.
Set theory is, alas, going to need to take a break.
Variety is good, though. In my discrete math class in college, graph theory was the only thing that inspired me to do anything outside of class (build a 3-D model of a 4-D hypercube). I’m sure there are lots of other potential readers who would stop by more regularly if there were a larger visual component.
You’ve been Tagged!
i need special problem in graph theory. i need your help. can you give me?