WEBVTT

00:00:09.036 --> 00:00:14.106
You'd have a hard time finding
Königsberg on any modern maps,

00:00:14.106 --> 00:00:17.415
but one particular quirk in its geography

00:00:17.415 --> 00:00:22.205
has made it one of the most famous cities
in mathematics.

00:00:22.205 --> 00:00:26.214
The medieval German city lay on both sides
of the Pregel River.

00:00:26.214 --> 00:00:28.875
At the center were two large islands.

00:00:28.875 --> 00:00:33.124
The two islands were connected 
to each other and to the river banks

00:00:33.124 --> 00:00:35.884
by seven bridges.

00:00:35.884 --> 00:00:41.296
Carl Gottlieb Ehler, a mathematician who
later became the mayor of a nearby town,

00:00:41.296 --> 00:00:44.395
grew obsessed with these islands
and bridges.

00:00:44.395 --> 00:00:47.205
He kept coming back to a single question:

00:00:47.205 --> 00:00:51.095
Which route would allow someone
to cross all seven bridges

00:00:51.095 --> 00:00:55.136
without crossing any of them
more than once?

00:00:55.136 --> 00:00:56.946
Think about it for a moment.

00:00:56.946 --> 00:00:57.936
7

00:00:57.936 --> 00:00:58.947
6

00:00:58.947 --> 00:00:59.916
5

00:00:59.916 --> 00:01:00.847
4

00:01:00.847 --> 00:01:01.956
3

00:01:01.956 --> 00:01:02.886
2

00:01:02.886 --> 00:01:03.996
1

00:01:03.996 --> 00:01:05.076
Give up?

00:01:05.076 --> 00:01:06.198
You should.

00:01:06.198 --> 00:01:07.513
It's not possible.

00:01:07.513 --> 00:01:12.636
But attempting to explain why
lead famous mathematician Leonhard Euler

00:01:12.636 --> 00:01:15.997
to invent a new field of mathematics.

00:01:15.997 --> 00:01:18.648
Carl wrote to Euler for help
with the problem.

00:01:18.648 --> 00:01:23.367
Euler first dismissed the question as
having nothing to do with math.

00:01:23.367 --> 00:01:25.136
But the more he wrestled with it,

00:01:25.136 --> 00:01:28.977
the more it seemed there might
be something there after all.

00:01:28.977 --> 00:01:32.906
The answer he came up with
had to do with a type of geometry

00:01:32.906 --> 00:01:38.258
that did not quite exist yet,
what he called the Geometry of Position,

00:01:38.258 --> 00:01:41.897
now known as Graph Theory.

00:01:41.897 --> 00:01:43.443
Euler's first insight

00:01:43.443 --> 00:01:48.507
was that the route taken between entering
an island or a riverbank and leaving it

00:01:48.507 --> 00:01:50.578
didn't actually matter.

00:01:50.578 --> 00:01:54.427
Thus, the map could be simplified with
each of the four landmasses

00:01:54.427 --> 00:01:56.627
represented as a single point,

00:01:56.627 --> 00:01:59.297
what we now call a node,

00:01:59.297 --> 00:02:04.198
with lines, or edges, between them
to represent the bridges.

00:02:04.198 --> 00:02:09.619
And this simplified graph allows us
to easily count the degrees of each node.

00:02:09.619 --> 00:02:13.219
That's the number of bridges 
each land mass touches.

00:02:13.219 --> 00:02:14.598
Why do the degrees matter?

00:02:14.598 --> 00:02:16.828
Well, according to the rules 
of the challenge,

00:02:16.828 --> 00:02:20.678
once travelers arrive onto a landmass
by one bridge,

00:02:20.678 --> 00:02:23.800
they would have to leave it 
via a different bridge.

00:02:23.800 --> 00:02:28.168
In other words, the bridges leading
to and from each node on any route

00:02:28.168 --> 00:02:30.587
must occur in distinct pairs,

00:02:30.587 --> 00:02:34.239
meaning that the number of bridges
touching each landmass visited

00:02:34.239 --> 00:02:36.368
must be even.

00:02:36.368 --> 00:02:40.029
The only possible exceptions would be
the locations of the beginning

00:02:40.029 --> 00:02:42.267
and end of the walk.

00:02:42.267 --> 00:02:47.218
Looking at the graph, it becomes apparent
that all four nodes have an odd degree.

00:02:47.218 --> 00:02:49.187
So no matter which path is chosen,

00:02:49.187 --> 00:02:53.440
at some point,
a bridge will have to be crossed twice.

00:02:53.440 --> 00:02:57.709
Euler used this proof to formulate
a general theory

00:02:57.709 --> 00:03:01.721
that applies to all graphs with two
or more nodes.

00:03:01.721 --> 00:03:05.790
A Eulerian path 
that visits each edge only once

00:03:05.790 --> 00:03:09.159
is only possible in one of two scenarios.

00:03:09.159 --> 00:03:13.769
The first is when there are exactly
two nodes of odd degree,

00:03:13.769 --> 00:03:16.310
meaning all the rest are even.

00:03:16.310 --> 00:03:19.659
There, the starting point is one
of the odd nodes,

00:03:19.659 --> 00:03:21.770
and the end point is the other.

00:03:21.770 --> 00:03:26.091
The second is when all the nodes
are of even degree.

00:03:26.091 --> 00:03:31.231
Then, the Eulerian path will start
and stop in the same location,

00:03:31.231 --> 00:03:34.758
which also makes it something called
a Eulerian circuit.

00:03:34.758 --> 00:03:38.460
So how might you create a Eulerian path
in Königsberg?

00:03:38.460 --> 00:03:39.302
It's simple.

00:03:39.302 --> 00:03:41.402
Just remove any one bridge.

00:03:41.402 --> 00:03:46.080
And it turns out, history created
a Eulerian path of its own.

00:03:46.080 --> 00:03:50.198
During World War II, the Soviet Air Force
destroyed two of the city's bridges,

00:03:50.198 --> 00:03:53.531
making a Eulerian path easily possible.

00:03:53.531 --> 00:03:57.291
Though, to be fair, that probably
wasn't their intention.

00:03:57.291 --> 00:04:00.781
These bombings pretty much wiped
Königsberg off the map,

00:04:00.781 --> 00:04:04.910
and it was later rebuilt 
as the Russian city of Kaliningrad.

00:04:04.910 --> 00:04:09.083
So while Königsberg and her seven bridges
may not be around anymore,

00:04:09.083 --> 00:04:13.361
they will be remembered throughout
history by the seemingly trivial riddle

00:04:13.361 --> 00:04:17.662
which led to the emergence of 
a whole new field of mathematics.