Colorful Mathematics: Part I
3. Face colorings
We can now replace a vertex of valence i in this diagram with a face with i sides, bounded by 3-valent vertices as shown in the diagram below: This construction results in a new plane graph which is 3-valent. If one can four-color the faces of this graph, then one can four-color the faces of the original graph by shrinking the faces shown in black down to a single vertex. Remember that faces that touch at a vertex, after the shrinking process, but do not share an edge, can be colored the same color. Some plane graphs have vertices of valence 1 or valence 2. One can also transform such graphs to new ones where the vertices of valence 1 and 2 are eliminated (this is done by creating faces with 1 side or 2 sides), and where the new "graph" (strictly speaking a multigraph) is plane and has only 3-valent vertices. Again, the original graph can be colored with four or fewer colors when the new one can. Thus, we can reduce the problem of coloring plane graphs with four or fewer colors to the problem of coloring plane 3-valent graphs with four or fewer colors. Mathematicians have been trained to take complex environments and transform them into new environments which are simpler or more highly structured. The hope is that it may be possible to make progress by getting a "handle" on a problem, thereby solving it after the transformation. If one is successful in this approach, one should not neglect to see if there are other interesting phenomena to be gleaned about the original situation after one has obtained the insight from the transformed one. |
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 |