Example 1

EXAMPLE 1 Parts of a Graph

We can use the graph in Figure 1.2 to help explain these technical terms. The graph shown has five vertices and eight edges. The vertices represent cities, and the edges represent nonstop airline routes between them. We see that there is a nonstop flight between Berlin and Rome, but no such flight between New York and Berlin. There are several paths that describe how a person might travel with this airline from New York to Rome. The path that seems most direct is New York, London, Rome. But New York, Miami, Rome is also a path with only one “stop.” Furthermore, New York, London, Berlin, Rome is a path. We can describe these three paths as NLR, NMR, NLBR.

Another path would be New York, Miami, London, Berlin, Rome, which can be written NMLBR. An example of a circuit is Miami, Rome, London, Miami. It is a circuit because the path starts and ends at the same vertex. This circuit can best be described in symbols by MRLM. Another example of a circuit in this graph would be LRBL, which is the circuit involving the cities London, Rome, Berlin, and back to London. In this chapter, we are especially interested in circuits, just as we are in real life. Most of us end our day in the same place that we start it—at home!

Figure 1.2: Figure 1.2 (a) The edges of the graph show nonstop routes that an airline might offer. (b) The graph in (a) redrawn without the accidental crossing.

Notice that the edges MB (which could also be denoted BM) and RL shown in Figure 1.2a meet at a point that has no label. Furthermore, this point does not have a dark dot. This is because this point does not represent a vertex of our graph; it does not represent a city. It arises as an “accidental” consequence of the way this diagram has been drawn. We could join M and B with a curved line segment so that the edges LR and MB do not cross, or redraw the diagram so as to avoid a crossing in this case. We will be working often in situations where graphs can be drawn without accidental crossings, and we will try to avoid such crossings when it is convenient to do so. However, there are infinitely many graphs for which—when they are drawn on a flat piece of paper—accidental crossings are unavoidable. (Figure 2.12 on page 52 is an example of such a graph.)