# Is graph theory a good model for Seven Bridges of Koenigsberg?

I've asked this question on MathSE, but apparently people over there don't like philosophy.

Seven Bridges of Koenigsberg is the problem whose solution (by Euler) gave a rise to graph theory and (later) topology. The goal is to determine whether there exists a walk through the seven bridges in Koenigsberg crossing every bridge exactly once. Eveyrone knows it, as it is mentioned possibly in every univeristy mathematics course covering elements of graph theory.

Leonhard Euler came up with the following intuition: The physical map of the city, the exact location of the bridges, distances don't matter. All that matters mathematically is just the list of which regions are connected by bridges.

We could easily imagine a wrong mathematical model of this problem. Yet, it's commonly believed we can accurately describe the problem using graph theory and provide a solution within this theory, that correctly answers the original problem. How to ensure that a mathematical theory can describe a given problem correctly? What criterion to use here? Is it okay if nobody finds any flaw in the mathematical model within one week? One month, year, ten years, one hundred years, a thousand years? There might come a counterexample tomorrow, showing that this is NOT the right model of the problem. Intuition often deceives us.

What do mathematicians and philosophers could say about it?

Some may argue that it's unthinkable it may be wrong. Yes, it's a very easy, natural transition from informal problem to its mathematical description. But we can give examples of more difficult problems to model mathematically that aren't that obvious. I've taken a decision support systems course. We took problems expressed in natural language and tried to model them and find an algorithmic solution. How 'correct' were the models we've come up with? Up to which point in complexity of problems should we trust our thoughts, imagination and intuition?

• This question has been asked before very recently (in the comments they even mention the bridges of Koenigsberg problem), but this other way of asking makes the philosophical problem stand out better. – Keelan Mar 9 '15 at 20:54

Of course there are important things left out of the mathematical model. Maybe one of the islands is inhabited by bears who will certainly eat anyone who tries to enter. Maybe one of the bridges is incapable of supporting the weight of a human. Maybe there's an eighth bridge that somehow nobody's noticed before.

I have a great deal of trouble seeing what the issue is here. No matter what you choose to talk about, it's always possible you've overlooked something important. Once that thing is pointed out, you might or might not be perfectly happy to continue ignoring it. That's why we generally like to run our arguments past other people --- because sometimes they notice things we haven't noticed.

Your question seems to be: "How can we be 100% certain of never overlooking anything we might care about?". The answer is that we can't, and the counter-question is "Why ever would you have thought that we could?"

Edited to add: In the particular case of the Konigsberg bridges, I am sure that Euler would have been perfectly happy to go right on ignoring the bears or the collapsible bridge, because he was never terribly interested in traversing the islands in the first place --- instead he was interested in the mathematical problem the islands inspired, and that problem would have remained interesting with or without its "real-world" counterpart.

• The other answer is "the whole point of a model is to abstract the problem from the real world, such that we can neglect irrelevant complicating factors, and hopefully generalise the result to other situations (where there will be other complicating factors)". – naught101 Mar 10 '15 at 0:57
• @WillO, so you essentially agree that a graph model of this problem can turn out to be wrong one day. You can't prove it won't. – user216094 Mar 10 '15 at 19:41
• @user216094: I reject your use of the word "wrong" in this context. I do, however, agree that anything anybody believes can turn out to be wrong one day. I'm kind of amazed that you find anything remarkable in that. – WillO Mar 10 '15 at 20:16
• By wrong I mean 'incorrectly representing the problem'. For instance, we may find a setting of n bridges arranged in certain way that we would be able to cross each of them exactly once. Whereas the answer to that problem after modeling it in terms of graph theory would be that it's impossible. It's unthinkable that it might happen, but the fact that neiter I or you can't imagine it doesn't mean it can't happen. – user216094 Mar 10 '15 at 20:38
• @user216094 As I said in my answer (which you seem to prefer to ignore), there's nothing remotely unthinkable about it. Since you're pretty clearly uninterested in anything but repeating the same blather, I won't be responding further. – WillO Mar 10 '15 at 22:29

Let's make this simpler. Are numbers a good way to model amounts of discrete objects? This sentence has fifty four letters including spaces. But does it? Does it really? Isn't it possible we've made a mistake, and numbers are not a good model of anything?

Welllllll.

Technically, yes. Practically, no. Nihilism just isn't a very effective life strategy.

So, on to the bridges. The description of the problem, along with properties of the connectedness of space as experienced by us, prevents any divergence between the solutions given from graph theory and the solutions available in real life.

If you want to check, you ask questions like the following: what land can I reach without crossing a bridge? Does being in some spot in that land prevent me from reaching some bridges that touch that land? (No, barriers are not part of the problem.) Every point on the land is thus equivalent, so we can replace it with its equivalence set (a single point) for the purposes of this particular problem. Now, regarding bridges: if you start at one end of the bridge and go to the other, is there any possible path you can take such that you end up on a land unconnected to some other land you reached by crossing that same bridge? (No, each bridge end is fully contained within one bit of land.) So you can replace the bridge with a line between two bits of land (i.e. two points).

This sort of reasoning can be made more precise if one wishes, but really, this is not at all hard if done with care by people who know how to do such things. Thus, the chance of error is exceedingly, vanishingly small, to the point that you should no more worry about that than that you could count the number of 'o's in the body of this answer. (117, by the way.)

• 'If you want to check, you ask questions like the following:...' ok, even if I ask a thousand questions with answers that support this model it doesn't rule out the possibility that I've missed a question that, when asked, would invalidate the model. – user216094 Mar 11 '15 at 13:51
• @user216094 - Same deal with this question: how many letters are between these quotes: "x". Nothing anyone can say can completely rule out the possibility that our model of this question is wrong, and that counting fails to capture the problem. – Rex Kerr Mar 11 '15 at 13:57
• Then all science is based on hypotheses that hasn't been refuted yet. I'm okay with it when it comes to physics, chemistry etc., but for some reason I believed mathematics is irrefutable. – user216094 Mar 11 '15 at 14:28
• @user216094 - Mathematics is irrefutable if you don't make mistakes. But you can't prove you haven't made a mistake (if you did, there might be a mistake in your proof). Really careful checking by many people is highly reliable, though. Again, it's not really worth worrying about that much unless you worry that you don't know how many Zs there are here: ZZZ. If you are worried about that, asking about bridges seems a distraction, no? – Rex Kerr Mar 11 '15 at 14:51
• Is it right to call that model of Seven Bridges problem an axiom? – user216094 Mar 11 '15 at 15:27

The loophole needed is that the original problem is phrased in a language. In our case, the language is English. English turns out to be a really poor language for discussing bridge crossings, so we turn to the language of math. We define a translation of the original problem (in English) into a new problem, defined purely in the language of mathematics. We then do the problem in mathematics, and translate the answer back into English.

Anyone is free to question whether the translation of the original problem fully captures the English version. Anyone is free to question the translation of the mathematical answer into English. In fact, this happens on a regular basis. Look up any "proofs" regarding omnipotence and omniscience and you'll see just how much people disagree on translations for these words.

As for the Koenigsberg bridge problem, I would argue that you could translate the problem into a topology problem (every point in the city has "neighbors"), then use math to perfectly translate that into the graph problem.

• Topology is again just another mathematical tool assumed to accurately represent our intuition. But you're trying to eliminate the issue by bringing a more problematic, abstract model of space and continuity (=more likely to be wrong) - topology. Again, it's believed to correctly capture our intuition. We cannot prove it does. If we try to explain things, we attempt to explain it using simpler terms and ideas. – user216094 Mar 12 '15 at 22:35
• That is true. Do note that most of my answer is on the linguistic problem, not the mathematical one. The math portion was just provided to tie it into your original question. I would argue that the direction you are looking at is not related to mathematics at all, but rather a few key words: "prove" "ensure" and "correct." Those terms are what I would focus on, and approaching them from a linguistic-philosophic direction, rather than a mathematical-philosophic direction. – Cort Ammon Mar 12 '15 at 23:54