Peter Alfeld, --- Department of Mathematics, --- College of Science --- University of Utah

Multivariate Splines and the 4 Color Map Problem


The discharging technique is essential to the proof of the 4 Color Map Theorem. A charge is applied to the vertices (or edges, or triangles) in such a manner that the total charge is known to be positive. The charge is then redistributed in such a way that the overall charge remains the same (and positive). Since the charge is positive there must be a configuration with a positive charge. By examining all ways in which positive charges can arise in the redistribution process a set of unavoidable configurations can be constructed.

Above is the first argument in this talk making use of discharging. The result itself can of course be obtained more directly:

Suppose each vertex is of degree at least 6. Since every edge has two endpoints, the total number of edges is at least

3V = 3VB + 3VI  

On the other hand, according to the combinatorics of a triangulation the total number of edges is

E = EI + EB = VB + 3VI - 3 + VB < 3VB + 3VI

which is a contradiction.