Subtitles section Play video Print subtitles 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...