This chapter introduces an area of mathematics called graph theory. We start with the application for which graph theory was first developed, in the eighteenth century.

Representing Roads: The Königsberg Bridges

Suppose your vacation is to be a road trip, visiting a number of towns by car. You will want to know the roads joining various towns in order to plan your itinerary.

Of course, road atlases are available, but if your only desire is to list the towns that will be visited, in order, you do not need to know all the information in the atlas,  such as the physical properties of the region—hills and so on—or whether different roads cross or there are overpasses. The important information is whether or not there is a road joining a given pair of towns. For this purpose it is sufficient to make a diagram as shown in Fig. 1.1a, that indicates roads joining B to C, A to each of B and C, and C to D, with no direct roads joining A to D or B to D.

                 Fig. 1.1 Representing a road system

There will often be a choice of routes between two towns. This information may be significant: you might prefer the freeway, which is faster, or you might prefer the more scenic coast road. In this case the diagram does not contain enough information. For example, if there had been two different ways to travel from B to C, this information could be represented as in the diagram of Fig. 1.1b. Then you could go further, and label the different roads with their estimated driving times, as shown in Fig. 1.1c.

Sample Problem 1.1 Suppose the road system connecting towns A, B and C consists of two roads from A to B, one road from B to C, and a bypass road directly from A to C. Represent this road system in a diagram.

Solution.

The sort of diagram shown in Fig. 1.1a is called a linear graph, or usually just a graph. The dots representing towns will be called vertices, while the lines representing the road links are called edges.

The study of graphs goes back to 1735, when the great Swiss mathematician Leonhard Euler gave a talk to the St. Petersburg Academy. The talk grew out of a famous old problem. The town of Königsberg in Prussia was built on the river Pregel.

The river divided the town into four parts, including an island called The Kneiphof,  and in the eighteenth century the town had seven bridges; the layout is shown in Fig. 1.2. The question under discussion was whether it is possible from any point on Konigsberg to take a walk in such a way as to cross each bridge exactly once.

Fig.1.2 The Königsberg bridges

In fact, it is impossible to walk over the bridges of Königsberg as required. To see this, let’s suppose there was such a walk. There are three bridges leading to the area C: you can traverse two of these, one leading into C and the other leading out,  at one time in your walk. There is only one bridge left: if you cross it going into C,  then you cannot leave C again, unless you use one of the bridges twice, so C must be the finish of the walk; if you cross it in the other direction, C must have been the start of the walk. So either C is the place where you started or it is the place where you finished—let’s call it an end of the walk.

We can make a similar analysis of parts A,B and D, since each has an odd number of bridges—five for B and three for the others. So each of A,B,C,D is either the start or the finish of the walk. But any walk starts at one place and finishes at one place; it

Fig. 1.3 Graph representing the Königsberg bridges

can start and finish at the same place, or there can be a start and a separate finish. But in either case there cannot be more than two ends; A,B,C and D cannot all be ends.

Euler started by finding a graph that models the Königsberg bridge problem  (considered as a road network, with the islands and riverbanks as separate “towns”).

Vertices A,B,C and D represent the parts A,B,C and D of Königsberg, and each bridge is represented by an edge. The graph is shown in Fig. 6.3. In terms of this model, the original problem becomes: can a walk be found that contains every edge of the graph precisely once?

Sample Problem 1.2 The islands A, B, C, D are joined by seven bridges—two joining A to B, two from C to D, and one each joining the pairs AC, AD and BD.

Represent the system graphically. Could one walk through this system, crossing each bridge exactly once?

Solution. Islands B and C each have an odd number of bridges, so one must be the start of the walk and the other the finish.

With a little experimentation you will find a solution—one example is BACDABDC, and there are others.