Colorful Mathematics: Part I
2. Basic ideas
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.
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:
(Used with the kind permission of Professor Ulrich Faigle)
The graph on the left is a complete graph with 5-vertices, denoted K5. The graph on the right is usually denoted K3,3. Note that K3,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.
Welcome to the
These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics.
Search Feature Column
Feature Column at a glance
Comments: Email Webmaster