Feature Column from the AMS

Colorful Mathematics: Part I

2. Basic ideas

Consider the diagram shown below:

Figure 1

This diagram is known as a graph, a geometric structure consisting of dots, called vertices, and line segments, called edges (in this example, straight line segments). Though sometimes the definition of a graph allows a vertex to be joined to itself by one or more edges (called loops), here a graph (usually) will not allow loops. Also, unless specifically stated, we will not allow two or more edges to join the same pair of vertices. In this case we would be allowing multiple edges and the geometric structure involved would be called a multigraph (which in the usual definition also allows loops). In discussing graphs (or multigraphs) it is also convenient to have a name for the number of edges that are present at a vertex. If there are k edges at a vertex, we will say the vertex is of degree k or is k-valent. (When loops are allowed, each loop adds two to the valence of a vertex.) The graph above has two 3-valent vertices and three 4-valent vertices. When a graph has all of its vertices 3-valent, it is known as a 3-valent or cubic graph.

We can interpret the diagram in Figure 1 as being a small piece of a plane, a small piece of a sphere, or a small piece of a torus. If, for the moment, we think of graphs drawn on a plane (in such a manner that edges meet only at vertices), the edges of the graph divide the plane into regions called faces. The graph above divides the plane into 6 regions, including one region that surrounds all the others, which is known as the infinite face or unbounded face. We can also count how many sides (line segments in the boundary) each face has. In Figure 1 all the faces have three sides.

I will use the word map in an informal way to suggest the graph plus the regions into which it divides the surface. I will also use the phrase plane graph to mean a graph which can be drawn in the plane so that its edges meet only at vertices. Plane graphs always have at least one face, the infinite face. Planar graphs are those which are isomorphic (i.e. have the same combinatorial structure) to graphs which can be drawn as plane graphs. Two graphs which are non-planar are shown below. No matter how hard one tries, one can not draw these graphs in the plane so that edges meet only at vertices.

The graph above models a common puzzle that is often shown to primary school students. One is given three houses, represented by the top row of vertices, and three utilities, represented by the bottom row of vertices. Can you find a way of joining the houses to the utilities so that connections are made with "cables" (edges) drawn in the plane which meet only at vertices? These graphs are known as the Kuratowski graphs because the Polish mathematician Kazimierz Kuratowski (1896-1980) showed that in a precise sense, every non-planar graph "contains" a copy of one of these two. For studying planarity and coloring problems associated with graphs, it has been very helpful to be able to start with one graph and transform it into another graph with related properties. Two such "operations" on graphs are deletion and contraction of edges. The diagrams below illustrate these two operations:

Deletion of an edge:

Note that the end vertices of the edge AB remain in the graph, while the edge AB itself gets erased. (The other segments shown are to suggest that other edges at A and at B are untouched.) Note also that one or more isolated vertices can result from an edge deletion depending on whether one or both of the vertices A and B are 1-valent.

Contraction of an edge:

When contracting an edge, the edge AB is squeezed until the vertices A and B coincide and become one vertex, dragging the edges that had been attached at A and at B along, so that they now combine to contribute to the valence at the new combined vertex. The edge AB can now be thought of as being a loop at the combined vertex, but usually this loop is considered to be thrown away as part of the contraction process. A slight variant would be to delete the edge from A to B before the squeezing together process, thereby avoiding the creation of a loop. Notice that if vertices A and B are joined to a third vertex C, thereby forming a circuit of length 3, then when the edge AB is contracted, the circuit CABC of length 3 becomes a circuit of length 2. For coloring the vertices of a graph, multiple edges have no effect because the two vertices joined by one or more edges must get different colors, so there is no loss in the contraction process for an edge to delete multiple edges (or loops) that are produced. Some mathematicians do not remove the multiple edges and loops in their definitions of edge contraction, thereby getting a multigraph rather than a graph when edges are contracted. These authors can remove "extra" multiple edges and loops by edge deletions.

Graph theory is often approached geometrically, by drawing dots in a plane and joining them with line segments, as we did above and in the graph below:

However, the subject can also be approached more abstractly. This is done by defining a set of objects called vertices and specifying which of these vertices are joined by edges. Edges are thought of as the pair of vertices joined. For example, the graph above can be specified by giving the set V of vertices, V = {0, 1, 2, 3} and the set E of edges, E = {(0,1), (2,1), (1,3), (2,3)}. Note that the edge (2,1) is the same as the edge (1,2). A graph from this point of view is sometimes called an abstract graph. Given an abstract graph, one can ask when it is possible to draw the graph on some surface, such as the plane, a torus (donut), two-holed torus, etc., so that edges only meet at vertices. The answer to this question, with regard to the plane, can be arrived at by purely combinatorial aspects of the graph's description. The best known result of this kind, as noted above, is called Kuratowski's Theorem. However, recently, there is a less well-known result, (Klaus) Wagner's Theorem, that has proved to be at least as valuable.

(Used with the kind permission of Professor Ulrich Faigle)

Theorem (Klaus Wagner, 1910-2000):

If an abstract graph G is not planar, then G has a subgraph H for which there is a sequence of edge contractions of H which gives rise to either of the two graphs below:

The graph on the left is a complete graph with 5-vertices, denoted K₅. The graph on the right is usually denoted K_3,3. Note that K_3,3 is 3-valent and, thus, despite the fact that it does not seem to be that dense in edges, is nonetheless not a planar graph. It is known that if a graph with V vertices (where V is at least three) has more than 3V - 6 edges, then the graph must be non-planar.