Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

What was the actual actual problem that led Euler to graph theory?

By looking even at non-simplified map like this

enter image description here

It is obvious that, if a landmass is connected by odd number of bridges, it cannot be only visited by crossing each bridge once - it must either be the start or the end of path. Here I see four landmasses with odd number of bridges, so it is obvious that there is no solution to the problem.

How could such a simple problem lead Euler to creating methods of analyzing such problem? And how could solution to such problem even get published?

My own guesses are that either mathematicians of the time were worried about some problems of rigour which I have missed or Euler just didn't imagine that the problem was unsolvable - instead he tried various unsuccesful paths and then simplified and reformulated the problem to get closer to the elusive solution.

share|improve this question

closed as not constructive by rschwieb, Julian Kuelshammer, Paul, DonAntonio, ShreevatsaR Apr 29 '13 at 8:33

As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center for guidance.If this question can be reworded to fit the rules in the help center, please edit the question.

9  
I guess this is as "obvious" as things falling down (say, apples falling from a tree), or as "obvious" as a closed curve (just like that) divides the plane in two components, one bounded and other one unbounded, or even as obvious as the heavier an object is the faster it falls down when dropped. This last was aristotelically obvious for almost 2,000 years...nowadays it is slightly less obvious. :P) –  DonAntonio Apr 28 '13 at 11:37
6  
I dare guess that most of the residents of Königsberg/Kaliningrad who thought about the problem didn't have a map at hand. I also dare guess that some smart person there also had figured out the fundamental obstacle. Euler gets the credit for formalizing and generalizing the ideas by compressing the problem from the network of streets and bridges down to bare essentials, i.e. the graph. I haven't studied history of math, so IDK, but it is not unheard of that whoever describes stories like this also resorts to creative license. –  Jyrki Lahtonen Apr 28 '13 at 11:44
6  
After reading the comments here, I wonder whether any other answer than "Yes, you, Juris, is smarter than Euler!" will satisfy you. –  Henning Makholm Apr 28 '13 at 13:18
1  
Well, no: Galileo was right and he proved Aristotle, and you, wrong, and this was some 400 years ago: both the feather and a 5 tons elephant (and of course, a hammer), when dropped from the same height and taking into account the air resistance, reach the floor at the very same time. you should be more careful with this historical and physical facts. –  DonAntonio Apr 28 '13 at 13:19
1  
Often, a great mathematician solves a problem. Later people find simpler solutions, but these do not detract from the achievement of the original solver. That said, I like your nice non-graph-theoretic proof. As with some of the very best proofs, it seems obvious once it has been digested. –  John Bentin Apr 28 '13 at 14:15

2 Answers 2

If you consider this problem trivial today, this is in part due to the fact that Euler created the language of graph theory that makes it easy to formulate this kinds of reasoning. Indeed the general fact that a connected graph admits an Eulerian path (if and) only if at most two vertices have odd degree is a very simple theorem of graph theory. But in Euler's time, mathematics simply did not have much language to discuss or solve this kinds of problems, so it is to the credit of Euler that he put in place the abstractions necessary to do these things cleanly. This was a more fundamental step than developing more involved theorems once the language is in place.

You may object that you did not need the language of graph theory to formulate an obstruction showing that the problem is unsolvable. Well, you may not have used the same language, but the argument is based exactly on the same abstractions that lead to graph theory. The very fact of formulating the problem in terms of landmasses (vertices) linked by bridges (edges), and reducing the route followed to a sequence of bridges crossed, is precisely the abstraction that makes the problem tractable, and indeed quite easy. You need not know about graph theory, or even be aware that you are doing this abstraction when formulating the obstruction, but if you try to analyse carefully what makes your argument work, you will find that in the end this abstraction is the crucial factor.

It seems unlikely many people cared about the seven bridges problem at all before Euler dealt with it. Or maybe some did, but after a bit of reflection concluded that there is (probably) no solution, and stopped worrying about it; history would certainly have forgotten them. The great insight of Euler is that a powerful abstraction is involved that can be applied very effectively to a wide range of more difficult problems.

Of course if Euler hadn't invented graph theory someone else would have; it is a fairly natural thing to do. But it happened to be Euler who did it first.

share|improve this answer
    
For a take on the assertion in the last sentence, one can google the words Let Platonism Die and read, inter alia, Davies's 2007 paper in the Newsletter of the EMS. –  Did Apr 28 '13 at 11:50
    
@Did: Although I am not naturally inclined to do as I'm told, I did just read that short paper. I thought initially you meant to imply that somebody else than Euler should be credited with inventing graph theory, but it seems nothing in the paper suggests such a thing, or even mentions Euler at all. Maybe you meant the claim that somebody would have invented graph theory if Euler hadn't; this is of course entirely speculative, but about as certain as that somebody (ore several people) would have stated Newton's laws of motion in some form if Newton hadn't. –  Marc van Leeuwen Apr 28 '13 at 12:12
1  
Your assumption that graph theory is what makes the problem trivial is not entirely correct. I have almost no knowledge about graphs and I even have trouble connecting between the bridge problem and that unnatural rearrangement in the graph upload.wikimedia.org/wikipedia/commons/6/61/… I really think that the problem is trivial and a graph is too complicated tool for such problem. Therefore it seems very strange that it was not only used, but created for this problem. –  Juris Apr 28 '13 at 12:23
1  
@Marc One should read "next-to-last sentence" in my previous comment, sorry for this mistake. (Unrelated: just for the record, I did not tell you to do anything and I have no idea how you got that notion.) –  Did Apr 28 '13 at 12:28

The abstraction to land mases with an odd/even number of bridges is already a step that is not totally obvious - otherwise people without any prior knowledge of graph theory or this specific problem would not go ahead and try to sketch attempted solutions with trial and error (and they do).

share|improve this answer
    
Maybe it's the formulation - when I first read about the problem, it asked whether a solution exists, so I saw that it doesn't. If it asked to find the solution, I'd probably start to sketch too :) –  Juris Apr 28 '13 at 12:16

Not the answer you're looking for? Browse other questions tagged or ask your own question.