Abstract: Our story begins almost 300 years ago in the city of Königsberg. The city was part of East Prussia. The river Pregel flowed through the city and created an island called Kniephof as shown in the diagram below. There were seven bridges on the river. A puzzle that the townsfolk wanted to solve was whether one could walk a trail in which each bridge is crossed but once and only once.

No one was able to find a trail and neither were they able to show that no such trail existed. It was the famous Mathematician Leonhard Euler who communicated the solution in 1736. He not only proved that such a trail was impossible but in the process nurtured the birth of Graph Theory.

In his paper, communicating the solution to the Königsberg Bridges Problem, titled `The solution of a problem relating to the geometry of position’, he says:

In addition to that branch of geometry which is concerned with magnitudes, and which has always received the greatest attention, there is another branch, previously almost unknown, which Leibniz first mentioned, calling it the geometry of position. This branch is concerned only with the determination of position and its properties; it does not involve measurements, nor calculations made with them…. I have therefore decided to give here the method which I have found for solving this kind of problem, as an example of the geometry of position.

In the lecture, I will give some insight into Euler’s original solution and then move on to the basics of Graph Theory required to prove a result, which gives a necessary and sufficient condition for whether solutions to the puzzles like the Königsberg Bridges.