ABSTRACT
A solution to a famous puzzle called the Ko¨nigsberg Bridge Problem appeared in a 1736 paper [68] of Leonhard Euler titled Solutio problematis ad geometriam situs pertenentis, whose English translation is The solution of a problem related to the geometry of position. As the title of the paper suggests, Euler was aware that he was dealing with a different kind of geometry, namely one in which position was the relevant feature, not distance. Indeed, this gave rise to a new subject which for many years was known as Analysis Situs – the Analysis of Position. In the 19th century, this subject became Topology, a word that first appeared in print in an 1847 paper titled Vorstudien zur Topologie (Preliminary Studies of Topology) written by Johann Listing, even though he had already used the word Topologie for ten years in correspondence. Many of Listing’s topological ideas were due to Carl Friedrich Gauss, who never published any papers in topology. Euler’s 1736 paper is also considered the beginning of graph theory. Over a century later, in 1857, William Rowan Hamilton introduced a game called the Icosian. The Ko¨nigsberg Bridge Problem and Hamilton’s game would give rise to two concepts in graph theory named after Euler and Hamilton. These concepts are the main subjects of the current chapter.
