Konigsberg bridges

Puler path A connected graph can be traversed in one path (W hich ends at the node where it began) ifall nodes have an even degree (sec the Konigsberg bridge problem. Section 2.4.1). 

We can now state the Euler theorem, which resolved the problem of the Konigsberg bridges. 

The problem of the Konigsberg bridges Diagram-tracing puzzles Mazes and labyrinths... 

FIGURE 3.11 Konigsberg bridges in 1736 (left), the associated multi-graph (middle), and its eulerian version (right) adapted from Refs. (Atanasiu, 1971 Putz et al., 2008b). 

At the time of Leonhard Ealer (the 18th century, Konigsberg had seven bridges across the Prcgcl river. Some of the townspeople wanted to know if there was a path through the town that allowed one to eross each of the seven bridges exactly once and finish at the starting point. 

Thus, the graph theory introduced by Euler in 1736 proved that it was not possible to walk through Konigsberg by crossing each bridge exactly once and ending up at the point where the path was started [36. ... 

The proof of this theorem, which is not difficult, will not be given here. Since the graph associated with the Konigsberg land-bridge connections has three vertices of odd degree, it cannot be unicursal (or traceable). Obviously it is not an Euler graph. 

Simon, S.R., and Konigsberg, W.H. (1966) Chemical modification of hemoglobins A study of conformation restraint by internal bridging. Proc. Natl. Acad. Sci. USA 56, 749. 

Figure 9.2 (a) The City of Konigsberg showing the seven bridges. The island of Kniephof is in the... 

Figure 5.1 Schematic presentation of town Konigsberg with its seven bridges and connections. The plan of the town (a) is converted into graphs (b and c), which are completely equivalent representation of the object in (5.1a) and between themselves in Graph Theory.

Figure 9.2 (a) The City of Konigsberg showing the seven bridges. The island of Kniephof is in the centre, (b) simplified map and, (c) topological representation where land masses are reduced to nodes and bridges are reduced to lines. 

FIGURE 1.4 Schematic map of the city of Konigsberg and its seven bridges. 

---