Basics of Graph Theory

Königsberg Bridge Puzzle

L. Euler (1736) published the first article on graph theory which contains a generalized solution to the puzzle of Königsberg. Königsberg was in eastern Prussia and now is a part of the Russian Federation. At the time of Euler, a river divided the city into a number of regions, as shown in Figure 1. The puzzle involved starting on any of the regions shown in Figure 1, and finding a tour in which each bridge is traversed exactly once, returning to the initial region. Euler was the first person who showed that it is impossible to find such a tour.

Figure 1.

Königsberg bridges problem

Analyzing the graph of Figure 1, it could be seen the bridges puzzle could be transformed to an easier form, where each region is represented by a vertex and each bridge by an edge that connects the two vertices representing the regions at the ends of the bridge. Then the puzzle becomes one of, starting at a vertex and making a tour of the resulting graph which crosses each edge exactly once and finally gets back to the original vertex. Euler showed that this is possible if, and only if, every vertex is connected with an even number of edges. On studying Figure 1 it could be seen that, every vertex is connected with an odd number of edges, that is, each region is connected with an odd number of bridges. Thus, from Euler’s result we can establish that the puzzle could not be solved. The matters raised here will be discussed in details in Chapter 7.

Euler Cycles and Euler Paths

Can we travel through the edges of a graph starting at a vertex and returning to it by traversing each edge of the graph exactly once? Similarly, can we travel through the edges of a graph starting from a vertex and returning to it while each vertex of graph is involved exactly once? Although these questions seem to be similar, the first question, which asks the existence of Euler edge on a graph, can be answered for all graphs, while the second question, which asks about existence of Hamiltonian edge in a graph, is quite difficult to solve.

• Definition 1: A simple path which contains every edge of a given graph G is an Euler path.

Recognizing Euler path in a graph is somehow easy. L. Euler presented some rules for determination of Euler paths when studying the Königsberg bridge problem. It can be shown that every vertex must have even number of edges (Bollobas, 1998).

Hamilton’s Game

W. R. Hamilton presented his famous puzzle to the world in 1856. Figure 2 shows the Hamilton’s dodecahedron, in which each point is labeled with the name of important cities. In this puzzle one must find a tour passing along the indicated edges, involving all vertices once. It is clear that it should return to the initial vertex. Although the Hamilton’s game is famous enough in mathematics, but was not a commercial success at all.

Figure 2.

Hamilton’s game

The original question of this puzzle is similar to that of Königsberg bridge problem: find a tour in the graph with a certain given property. Königsberg property was: pass along each edge exactly once. Hamilton property is: pass through each point exactly once. Although the former has a quite simple characterization, but no reasonable characterization is known for the latter problem (Foulds, 1992). Detailed discussions on these graphs will be presented in the next chapters.