0:00:09.036,0:00:14.106 You'd have a hard time finding[br]Königsberg on any modern maps, 0:00:14.106,0:00:17.415 but one particular quirk in its geography 0:00:17.415,0:00:22.205 has made it one of the most famous cities[br]in mathematics. 0:00:22.205,0:00:26.214 The medieval German city lay on both sides[br]of the Pregel River. 0:00:26.214,0:00:28.875 At the center were two large islands. 0:00:28.875,0:00:33.124 The two islands were connected [br]to each other and to the river banks 0:00:33.124,0:00:35.884 by seven bridges. 0:00:35.884,0:00:41.296 Carl Gottlieb Ehler, a mathematician who[br]later became the mayor of a nearby town, 0:00:41.296,0:00:44.395 grew obsessed with these islands[br]and bridges. 0:00:44.395,0:00:47.205 He kept coming back to a single question: 0:00:47.205,0:00:51.095 Which route would allow someone[br]to cross all seven bridges 0:00:51.095,0:00:55.136 without crossing any of them[br]more than once? 0:00:55.136,0:00:56.946 Think about it for a moment. 0:00:56.946,0:00:57.936 7 0:00:57.936,0:00:58.947 6 0:00:58.947,0:00:59.916 5 0:00:59.916,0:01:00.847 4 0:01:00.847,0:01:01.956 3 0:01:01.956,0:01:02.886 2 0:01:02.886,0:01:03.996 1 0:01:03.996,0:01:05.076 Give up? 0:01:05.076,0:01:06.198 You should. 0:01:06.198,0:01:07.513 It's not possible. 0:01:07.513,0:01:12.636 But attempting to explain why[br]led famous mathematician Leonhard Euler 0:01:12.636,0:01:15.997 to invent a new field of mathematics. 0:01:15.997,0:01:18.648 Carl wrote to Euler for help[br]with the problem. 0:01:18.648,0:01:23.367 Euler first dismissed the question as[br]having nothing to do with math. 0:01:23.367,0:01:25.136 But the more he wrestled with it, 0:01:25.136,0:01:28.977 the more it seemed there might[br]be something there after all. 0:01:28.977,0:01:32.906 The answer he came up with[br]had to do with a type of geometry 0:01:32.906,0:01:38.258 that did not quite exist yet,[br]what he called the Geometry of Position, 0:01:38.258,0:01:41.897 now known as Graph Theory. 0:01:41.897,0:01:43.443 Euler's first insight 0:01:43.443,0:01:48.507 was that the route taken between entering[br]an island or a riverbank and leaving it 0:01:48.507,0:01:50.578 didn't actually matter. 0:01:50.578,0:01:54.427 Thus, the map could be simplified with[br]each of the four landmasses 0:01:54.427,0:01:56.627 represented as a single point, 0:01:56.627,0:01:59.297 what we now call a node, 0:01:59.297,0:02:04.198 with lines, or edges, between them[br]to represent the bridges. 0:02:04.198,0:02:09.619 And this simplified graph allows us[br]to easily count the degrees of each node. 0:02:09.619,0:02:13.219 That's the number of bridges [br]each land mass touches. 0:02:13.219,0:02:14.598 Why do the degrees matter? 0:02:14.598,0:02:16.828 Well, according to the rules [br]of the challenge, 0:02:16.828,0:02:20.678 once travelers arrive onto a landmass[br]by one bridge, 0:02:20.678,0:02:23.800 they would have to leave it [br]via a different bridge. 0:02:23.800,0:02:28.168 In other words, the bridges leading[br]to and from each node on any route 0:02:28.168,0:02:30.587 must occur in distinct pairs, 0:02:30.587,0:02:34.239 meaning that the number of bridges[br]touching each landmass visited 0:02:34.239,0:02:36.368 must be even. 0:02:36.368,0:02:40.029 The only possible exceptions would be[br]the locations of the beginning 0:02:40.029,0:02:42.267 and end of the walk. 0:02:42.267,0:02:47.218 Looking at the graph, it becomes apparent[br]that all four nodes have an odd degree. 0:02:47.218,0:02:49.187 So no matter which path is chosen, 0:02:49.187,0:02:53.440 at some point,[br]a bridge will have to be crossed twice. 0:02:53.440,0:02:57.709 Euler used this proof to formulate[br]a general theory 0:02:57.709,0:03:01.721 that applies to all graphs with two[br]or more nodes. 0:03:01.721,0:03:05.790 A Eulerian path [br]that visits each edge only once 0:03:05.790,0:03:09.159 is only possible in one of two scenarios. 0:03:09.159,0:03:13.769 The first is when there are exactly[br]two nodes of odd degree, 0:03:13.769,0:03:16.310 meaning all the rest are even. 0:03:16.310,0:03:19.659 There, the starting point is one[br]of the odd nodes, 0:03:19.659,0:03:21.770 and the end point is the other. 0:03:21.770,0:03:26.091 The second is when all the nodes[br]are of even degree. 0:03:26.091,0:03:31.231 Then, the Eulerian path will start[br]and stop in the same location, 0:03:31.231,0:03:34.758 which also makes it something called[br]a Eulerian circuit. 0:03:34.758,0:03:38.460 So how might you create a Eulerian path[br]in Königsberg? 0:03:38.460,0:03:39.302 It's simple. 0:03:39.302,0:03:41.402 Just remove any one bridge. 0:03:41.402,0:03:46.080 And it turns out, history created[br]a Eulerian path of its own. 0:03:46.080,0:03:50.198 During World War II, the Soviet Air Force[br]destroyed two of the city's bridges, 0:03:50.198,0:03:53.531 making a Eulerian path easily possible. 0:03:53.531,0:03:57.291 Though, to be fair, that probably[br]wasn't their intention. 0:03:57.291,0:04:00.781 These bombings pretty much wiped[br]Königsberg off the map, 0:04:00.781,0:04:04.910 and it was later rebuilt [br]as the Russian city of Kaliningrad. 0:04:04.910,0:04:09.083 So while Königsberg and her seven bridges[br]may not be around anymore, 0:04:09.083,0:04:13.361 they will be remembered throughout[br]history by the seemingly trivial riddle 0:04:13.361,0:04:17.662 which led to the emergence of [br]a whole new field of mathematics.