ABSTRACT
Many of the early concepts and theorems of graph theory came about quite indirectly, often from recreational mathematics, through puzzles or games, or problems that, as were seen later, could be phrased in terms of graphs. The very first of these was a puzzle called the Ko¨nigsberg Bridge Problem, which was not only solved by one of the most famous mathematicians of all time but whose solution is considered the origin of graph theory. Over a century later a game called the Icosian was invented by a well-known mathematician, knighted for his contribution to physics, and this too would prove to have close connections to graph theory. This puzzle and game would give rise to two important concepts in graph theory. It is these concepts that are the major topics of this chapter.
Early in the 18th century, the East Prussian city of Ko¨nigsberg (now called Kaliningrad and located in Russia) occupied both banks of the River Pregel and the island of Kneiphof, lying in the river at a point where it branches into two parts. There were seven bridges that spanned various sections of the river. (See Figure 3.1.)
