People living in Königsberg, in what is now Russia or Poland... Hard to say which. They had seven bridges across two shores of the Pregel River and there's [sic] two islands! One island here... An island over here... Bluh Bank over here, bank over here. And they've got it set up so that there's seven bridges. One, two... So you could go, you know, you'll wanna walk over this way. You could take a horse
and bug over to that side, cross over here, cross over here, and cross over here. One, two, three, four, five, six, seven bridges! People argued: "Can you take a Sunday walk and just cross every bridge once?" So, I wanna go out someday and just walk across this bridge, walk across this bridge, walk this bridge... Ah, I'll go this way this time! Walk across here, walk across here... Oops! I can't do it, 'cause I've already crossed those and I've left one. I don't care where I start and where I stop. But can I cross every bridge one time? People argued about it. Nobody was able to do it. Euler's at Saint Petersburg, working for the tsars, and he hears about this problem. And up until then people had said: "Well, we have to make a list" "of all possible ways to do this." "We have to try here, go there..." [sound of a series of choices] And in this wonderful paper that Euler writes, he says, Trying to solve it, one at a time, doesn't tell us anything new. It's today what we would call a numerical solution. That might give you an answer, but it doesn't give you understanding. He's saying, "Hm, how do I do this, ahn?" And then, he says, "Think about ordinary bridges." Every time I walk across a bridge onto an island, I go from Blue to Polka Dot Land... Oh, Blue to Polka Dot Land, Polka Dot Land to Red, the Red Shore over to Polka Dot Land... Oh, okay. Euler resigned concentrating on the bridges, starts saying, "Look at the islands, look at the landmasses." "Let's label those and think about that." So he goes over and says, "I'll label them." Oh, okay. I'll label, what I call Polka Dot Ville, I'll call that A. I'll reach my pocket and call that B over here. Over here, this side, let's call it C. And, oh! Look at this! There's D. I shouldn't be walking in the water. I should just stay on the b... In fact, I can't do that. I ought to just stay on the bridges the whole time. Keep me honest, you, Brady. Ahn... [Brady]: Oh, you stepped on the water. Oh! Opa pa pa! Let's make it real simple. If I have nothing but a bridge going from C to D to B. Let's start from C to D. Po po popopo... Ok, that's legal. So I have C -> D. Then I go from D to B. Oh, it's D -> B. Every time I get from one to another, from one landmass to another landmass, I can make a list -- of -- my -- travels. Oh! Oops, stay out of the water! Euler says, "This means that" "if I have even number of bridges," "one-one," "going into and out of an island," "that's completely legal." I can go right through the island if I have two or if I have four bridges... Oh, you can come across here, come across here, back, over, and back. But an *odd* number of bridges... Okay... I can come across here, and come across here... But I'm stuck! Go this way, turn around, but I haven't crossed this one. Alternatively, I could start on yellow... on D, walk this way, come back here, and then walk out here. Euler says, "Oh!" "If I have an odd number of bridges" "to any or from any island, I have to either" "start my walk at that location" "or end my walk at that location." Right now, island A has two bridges going to it. That means, oh, if I do not start on this island, I can just traverse it. You know, Euler goes on and says, "And if I start in that island," "I can go around -- blah, blah, blah" "Vu vu vuf -- and return to it." Even numbered islands, islands that have an even number
of bridges going to 'em. I've got it made! This makes it possible for me to -- to -- to-- almost eliminate them from my thought process. And it works whether it's two, four, or even... Or even six. Ok, got that one. Any landmasses, any place that has a bridge connected to it, if it has an even number of bridges -- oh! Easy! Piece of cake. If it has an odd number of bridges, then it's a special case. Clearly, if there is just one landmass that has an odd number of bridges, I can start on it, but I won't be able
to get back to it to stop on it. But if I have two islands that have
an odd number of bridges leading to them, I can start on one, traverse around, and then end on the other one. Now, let's go back to what was really
happening in Königsberg around 1725. Seven bridges, remember? Wasn't arranged like this. It was... One, two, three, four, five, six, seven. Ok. Let me see... [splashing water sound] Let me see how I'm doing. This section, the Red Shore, what he calls C, I have -- one, two -- three bridges from. [Brady]: Odd. Oh, it's and odd number! Odd number! Okay. How about D? Let go over D, island D. One, two -- three bridges. Oh, this is odd. How about... The North Shore, B? One, two, three -- odd number. What about island A? One, two, three, four -- five! An odd number. All of this landmasses have an
odd number of bridges leading to 'em. Euler says, "Nuh-uh," "none of them have an even number of bridges." "All are odd." No matter where you start, you cannot traverse all those bridges. ∎ Along, comes World War II: bomber attacks. Horrible! Just a desperately horrible situation. Two of these bridges get destroyed. The town is devastated, but at the end of the war, there's five bridges left. So, in a sense, today there's no Seven Bridges of Königsberg anymore. Not only there are not seven bridges, the city of Königsberg doesn't exist. It's been renamed to Kaliningrad. It's a part of Russia today. Or I think the Baltic Fleet works out of there. And there's five bridges. Well... Suppose you're sitting around in
today's city. Could you do this? Well, before even trying, let's just note: C over here, node C, this landmass of C, has two bridges today. An even number. Over there, the landmass B, the blue one, has one, two bridges from it. What about island A? One, two, three bridges, an odd number. Island D -- one, two -- three bridges. Oh! Thus, today there is no problem! From what Euler said, we could
start on either of the odd-bridged islands. So I can start here, and I'll end there. I have to choose a path that takes me
from here to there. Ok. I'll go like this: (Po po po po) Crossed one bridge. Crossed two bridge. I'll walk across my third bridge backwards. Walk across the fourth bridge forwards, back to where I started, but wait! There's one more bridge. (Po po po po) I've traversed the entire path. Started there, ended there. Euler has told us that, if there are exactly two islands that have an odd number of bridges, you have to start on one of them
and end on the other one. If there were three islands that had,
each had an odd number of bridges, no way! You couldn't solve the problem. However, if each island had
an even number of bridges... Suppose next week there's an earthquake. At the Baltic Sea, it knocks down one bridge. Now, every landmass has
two bridges going to it. And even I can figure it out, oh, yeah, I can traverse them all. Here's the first one, here's the second one, here's the third one, here's the fourth one. I traversed them all without any problem at all. Ok, suppose we only have
three bridges today. [Brady]: Another earthquake. Another earthquake happens! Ahh! Another bridge falls down! Now, Island A has one bridge
leading to it: an odd number. North Shore B has two bridges
leading to it: even. D over here, Island D has two bridges and C, where I'm standing,
has only one bridge on it. In this case, Euler tells us, yes,
we can still make a circuit that crosses all three bridges but we have to start on
an odd-numbered place and end on an odd number. So, I'm on the odd-numbered C, there's only one bridge,
one is an odd number. Okay -- (po po po po!) Got to D. D is an even one. Oh, ok. I'll walk across this one. (Pop pa!) And then I get to B and, oh, I can walk across this. I end up on an odd-bridged island and have completed traversed it. If all the islands have an even number of bridges, even everywhere! Then, we're even-Steven, piece of cake. You can make this traverse and
everybody in the saloon, in their Sunday walks, they're happy! What if there's only one
odd-numbered island? Turns out you can't make such a thing. If I have... Consider just one bridge. I have an island here, oh,
it's got an odd number o' bridges. But, oh, here's a second island
that has an odd number of bridges. I can't... I could sort of send it up into the air or it could have, you know,
goes out into the water, you walk the plank. But no, for a legitimate bridge, if there's one odd, there has to be
another matching somewhere on the graph. So, Euler showed that this
bridge problem is kind of cool. So if you're in a saloon or
going out on a Sunday walk, it is nice to know -- oh, I can or can't
complete the circuit. Who cares? Well, you can't pick up a book on
discrete mathematics... Discrete mathematics and its applications... Discrete mathematics and computer science... Discrete mathematics with ducks... You can't touch a book on this without turning to a page that has Euler on it! And sure enough, over here, "The Swiss mathematician, Leonhard Euler,
solves this problem -- blah blah blah" Euler invented graph theory. This is the first time, 1830 [sic],
that graph theory has been thought of. And instead of analyzing this as a
"let's walk across bridges", Euler recognized that... That connections from one place to another were central to a part of mathematics. Even cooler than that! Euler said, "This is a geometric problem" "that has no triangles, it doesn't have
hypotenuses in it." It's what he called
a geometry problem of location. This was the beginning of topology. Euler's solution for this created graph theory. Euler's solution to this created topology. All this from a guy who, "Oh, yeah, I got a little bit of time" "to think about a problem that I heard about
from people going out on Sunday walks." That's brilliant. [Credits] Thank you to Audible for supporting this video. Audible is the top provider of audio books and other spoken material with a dizzying number of titles covering almost anything you can think of. If you don't believe me, here are just
seven bridge books you might enjoy listening to. Bridge of Spies, The Ice Bridge, Bridge to Terabithia, A Bridge Too Far, The Invisible Bridge, Bridget Jone's Diary and, my personal favorite
on this list, The Great Bridge: The epic history of the building of the Brooklin Bridge. And I've said bridge a lot of times. If you'd like to listen to any other books from Audible, you can sign up for a free month trial, which will include your first book for no charge. Audible is a great service, that've got
a super app for your phone and it's really easy to exchange a book if you end up
with one that doesn't take you fancy. To give them a try, go to Audible.com/numberphile. Thatwise, they'll know you came from here. And now thanks to them for supporting this video.
