Got a YouTube account?

New: enable viewer-created translations and captions on your YouTube channel!

English subtitles

← How the Königsberg bridge problem changed mathematics - Dan Van der Vieren

Get Embed Code
22 Languages

Showing Revision 2 created 08/19/2016 by Jessica Ruby.

  1. You'd have a hard time finding
    Königsberg on any modern maps,
  2. but one particular quirk in its geography
  3. has made it one of the most famous cities
    in mathematics.
  4. The medieval German city lay on both sides
    of the Pregel River.
  5. At the center were two large islands.
  6. The two islands were connected
    to each other and to the river banks
  7. by seven bridges.
  8. Carl Gottlieb Ehler, a mathematician who
    later became the mayor of a nearby town,
  9. grew obsessed with these islands
    and bridges.
  10. He kept coming back to a single question:
  11. Which route would allow someone
    to cross all seven bridges
  12. without crossing any of them
    more than once?
  13. Think about it for a moment.
  14. 7
  15. 6
  16. 5
  17. 4
  18. 3
  19. 2
  20. 1
  21. Give up?
  22. You should.
  23. It's not possible.
  24. But attempting to explain why
    led famous mathematician Leonhard Euler
  25. to invent a new field of mathematics.
  26. Carl wrote to Euler for help
    with the problem.
  27. Euler first dismissed the question as
    having nothing to do with math.
  28. But the more he wrestled with it,
  29. the more it seemed there might
    be something there after all.
  30. The answer he came up with
    had to do with a type of geometry
  31. that did not quite exist yet,
    what he called the Geometry of Position,
  32. now known as Graph Theory.
  33. Euler's first insight
  34. was that the route taken between entering
    an island or a riverbank and leaving it
  35. didn't actually matter.
  36. Thus, the map could be simplified with
    each of the four landmasses
  37. represented as a single point,
  38. what we now call a node,
  39. with lines, or edges, between them
    to represent the bridges.
  40. And this simplified graph allows us
    to easily count the degrees of each node.
  41. That's the number of bridges
    each land mass touches.
  42. Why do the degrees matter?
  43. Well, according to the rules
    of the challenge,
  44. once travelers arrive onto a landmass
    by one bridge,
  45. they would have to leave it
    via a different bridge.
  46. In other words, the bridges leading
    to and from each node on any route
  47. must occur in distinct pairs,
  48. meaning that the number of bridges
    touching each landmass visited
  49. must be even.
  50. The only possible exceptions would be
    the locations of the beginning
  51. and end of the walk.
  52. Looking at the graph, it becomes apparent
    that all four nodes have an odd degree.
  53. So no matter which path is chosen,
  54. at some point,
    a bridge will have to be crossed twice.
  55. Euler used this proof to formulate
    a general theory
  56. that applies to all graphs with two
    or more nodes.
  57. A Eulerian path
    that visits each edge only once
  58. is only possible in one of two scenarios.
  59. The first is when there are exactly
    two nodes of odd degree,
  60. meaning all the rest are even.
  61. There, the starting point is one
    of the odd nodes,
  62. and the end point is the other.
  63. The second is when all the nodes
    are of even degree.
  64. Then, the Eulerian path will start
    and stop in the same location,
  65. which also makes it something called
    a Eulerian circuit.
  66. So how might you create a Eulerian path
    in Königsberg?
  67. It's simple.
  68. Just remove any one bridge.
  69. And it turns out, history created
    a Eulerian path of its own.
  70. During World War II, the Soviet Air Force
    destroyed two of the city's bridges,
  71. making a Eulerian path easily possible.
  72. Though, to be fair, that probably
    wasn't their intention.
  73. These bombings pretty much wiped
    Königsberg off the map,
  74. and it was later rebuilt
    as the Russian city of Kaliningrad.
  75. So while Königsberg and her seven bridges
    may not be around anymore,
  76. they will be remembered throughout
    history by the seemingly trivial riddle
  77. which led to the emergence of
    a whole new field of mathematics.