1
00:00:09,036 --> 00:00:14,106
You'd have a hard time finding
Königsberg on any modern maps,

2
00:00:14,106 --> 00:00:17,415
but one particular quirk in its geography

3
00:00:17,415 --> 00:00:22,205
has made it one of the most famous cities
in mathematics.

4
00:00:22,205 --> 00:00:26,214
The medieval German city lay on both sides
of the Pregel River.

5
00:00:26,214 --> 00:00:28,875
At the center were two large islands.

6
00:00:28,875 --> 00:00:33,124
The two islands were connected 
to each other and to the river banks

7
00:00:33,124 --> 00:00:35,884
by seven bridges.

8
00:00:35,884 --> 00:00:41,296
Carl Gottlieb Ehler, a mathematician who
later became the mayor of a nearby town,

9
00:00:41,296 --> 00:00:44,395
grew obsessed with these islands
and bridges.

10
00:00:44,395 --> 00:00:47,205
He kept coming back to a single question:

11
00:00:47,205 --> 00:00:51,095
Which route would allow someone
to cross all seven bridges

12
00:00:51,095 --> 00:00:55,136
without crossing any of them
more than once?

13
00:00:55,136 --> 00:00:56,946
Think about it for a moment.

14
00:00:56,946 --> 00:00:57,936
7

15
00:00:57,936 --> 00:00:58,947
6

16
00:00:58,947 --> 00:00:59,916
5

17
00:00:59,916 --> 00:01:00,847
4

18
00:01:00,847 --> 00:01:01,956
3

19
00:01:01,956 --> 00:01:02,886
2

20
00:01:02,886 --> 00:01:03,996
1

21
00:01:03,996 --> 00:01:05,076
Give up?

22
00:01:05,076 --> 00:01:06,198
You should.

23
00:01:06,198 --> 00:01:07,513
It's not possible.

24
00:01:07,513 --> 00:01:12,636
But attempting to explain why
led famous mathematician Leonhard Euler

25
00:01:12,636 --> 00:01:15,997
to invent a new field of mathematics.

26
00:01:15,997 --> 00:01:18,648
Carl wrote to Euler for help
with the problem.

27
00:01:18,648 --> 00:01:23,367
Euler first dismissed the question as
having nothing to do with math.

28
00:01:23,367 --> 00:01:25,136
But the more he wrestled with it,

29
00:01:25,136 --> 00:01:28,977
the more it seemed there might
be something there after all.

30
00:01:28,977 --> 00:01:32,906
The answer he came up with
had to do with a type of geometry

31
00:01:32,906 --> 00:01:38,258
that did not quite exist yet,
what he called the Geometry of Position,

32
00:01:38,258 --> 00:01:41,897
now known as Graph Theory.

33
00:01:41,897 --> 00:01:43,443
Euler's first insight

34
00:01:43,443 --> 00:01:48,507
was that the route taken between entering
an island or a riverbank and leaving it

35
00:01:48,507 --> 00:01:50,578
didn't actually matter.

36
00:01:50,578 --> 00:01:54,427
Thus, the map could be simplified with
each of the four landmasses

37
00:01:54,427 --> 00:01:56,627
represented as a single point,

38
00:01:56,627 --> 00:01:59,297
what we now call a node,

39
00:01:59,297 --> 00:02:04,198
with lines, or edges, between them
to represent the bridges.

40
00:02:04,198 --> 00:02:09,619
And this simplified graph allows us
to easily count the degrees of each node.

41
00:02:09,619 --> 00:02:13,219
That's the number of bridges 
each land mass touches.

42
00:02:13,219 --> 00:02:14,598
Why do the degrees matter?

43
00:02:14,598 --> 00:02:16,828
Well, according to the rules 
of the challenge,

44
00:02:16,828 --> 00:02:20,678
once travelers arrive onto a landmass
by one bridge,

45
00:02:20,678 --> 00:02:23,800
they would have to leave it 
via a different bridge.

46
00:02:23,800 --> 00:02:28,168
In other words, the bridges leading
to and from each node on any route

47
00:02:28,168 --> 00:02:30,587
must occur in distinct pairs,

48
00:02:30,587 --> 00:02:34,239
meaning that the number of bridges
touching each landmass visited

49
00:02:34,239 --> 00:02:36,368
must be even.

50
00:02:36,368 --> 00:02:40,029
The only possible exceptions would be
the locations of the beginning

51
00:02:40,029 --> 00:02:42,267
and end of the walk.

52
00:02:42,267 --> 00:02:47,218
Looking at the graph, it becomes apparent
that all four nodes have an odd degree.

53
00:02:47,218 --> 00:02:49,187
So no matter which path is chosen,

54
00:02:49,187 --> 00:02:53,440
at some point,
a bridge will have to be crossed twice.

55
00:02:53,440 --> 00:02:57,709
Euler used this proof to formulate
a general theory

56
00:02:57,709 --> 00:03:01,721
that applies to all graphs with two
or more nodes.

57
00:03:01,721 --> 00:03:05,790
A Eulerian path 
that visits each edge only once

58
00:03:05,790 --> 00:03:09,159
is only possible in one of two scenarios.

59
00:03:09,159 --> 00:03:13,769
The first is when there are exactly
two nodes of odd degree,

60
00:03:13,769 --> 00:03:16,310
meaning all the rest are even.

61
00:03:16,310 --> 00:03:19,659
There, the starting point is one
of the odd nodes,

62
00:03:19,659 --> 00:03:21,770
and the end point is the other.

63
00:03:21,770 --> 00:03:26,091
The second is when all the nodes
are of even degree.

64
00:03:26,091 --> 00:03:31,231
Then, the Eulerian path will start
and stop in the same location,

65
00:03:31,231 --> 00:03:34,758
which also makes it something called
a Eulerian circuit.

66
00:03:34,758 --> 00:03:38,460
So how might you create a Eulerian path
in Königsberg?

67
00:03:38,460 --> 00:03:39,302
It's simple.

68
00:03:39,302 --> 00:03:41,402
Just remove any one bridge.

69
00:03:41,402 --> 00:03:46,080
And it turns out, history created
a Eulerian path of its own.

70
00:03:46,080 --> 00:03:50,198
During World War II, the Soviet Air Force
destroyed two of the city's bridges,

71
00:03:50,198 --> 00:03:53,531
making a Eulerian path easily possible.

72
00:03:53,531 --> 00:03:57,291
Though, to be fair, that probably
wasn't their intention.

73
00:03:57,291 --> 00:04:00,781
These bombings pretty much wiped
Königsberg off the map,

74
00:04:00,781 --> 00:04:04,910
and it was later rebuilt 
as the Russian city of Kaliningrad.

75
00:04:04,910 --> 00:04:09,083
So while Königsberg and her seven bridges
may not be around anymore,

76
00:04:09,083 --> 00:04:13,361
they will be remembered throughout
history by the seemingly trivial riddle

77
00:04:13,361 --> 00:04:17,662
which led to the emergence of 
a whole new field of mathematics.