ABSTRACT
Some say that graph theory was born in the city of Königsberg, located on the banks of the Pregel. The river surrounded the island of Kneiphof, and there were seven bridges linking the four land masses of the city, as illustrated in Figure 5.1a. It seems that the residents wanted to know whether it was possible to take a stroll from home, cross every bridge exactly once, and return home. The problem reduces to traversing the graph in Figure 5.1b, where the vertices represent land masses and the edges represent bridges. We want to know when a graph contains a single closed trail traversing all its edges.
