By a map we shall mean what is usually meant by a map of a continent (showing countries) or a country (showing states or provinces). However we shall make one restriction. Sometimes one state can consist of two disconnected parts (in the United States, Michigan consists of two separate land masses, unless we consider manmade constructions such as the Mackinaw Bridge). We shall exclude such cases from consideration; in our discussion, any state, or any country, will be a connected area.

Given a map, we can construct a graph as follows: the vertices are the countries or states on the map, and the two vertices are joined by an edge precisely when the corresponding countries have a common borderline. You can draw the graph on top of the map by putting a vertex inside each state and joining vertices by edges that pass through common state borders, so the graph of any map is planar. On the other hand, any planar graph is easily represented by a map.

Sample Problem1.1 Represent the map of the mainland of Australia, divided into states and the Northern Territory, as a graph.

Solution. The map is shown, for reference, alongside its graph.

Sometimes two states have only one point in common. An example, in the United States, occurs where Utah and New Mexico meet at exactly one point, as do Colorado and Arizona. We shall say that states with only one point in common have no border, and treat them as if they do not touch.