Unknown

2.2. Division of Polynomials 61

(c) In (b), argue that

P(h)..., tn) -q(s1,s2 ,..., h-1)

is a symmetric polynomial which vanishes for t, = 0, and hence

vanishes when any of the variables ti is individually set equal to

0.

(d) Show that the polynomial p - q in (c) either vanishes or can be

written as the product of tit2... t, and a homogeneous symmet-

ric polynomial of degree k - n, and use this fact along with the

induction hypothesis to complete the proof of Gauss’ Theorem.

Explorations

E.19. Chromatic Polynomials. One of the most notorious problems of
all time is the Four Color Problem. Suppose that you are given any map
drawn upon a sphere; every region is such that you can pass from any point
in the region to any other without having to leave the region (technically,
any two points in a region can be connected by an arc in the region). One
wishes to color this map in such a way that any two regions which have
a common boundary line are colored differently. With some maps, such as
those like a checkerboard, two colors will be enough. Other maps, such as
the map of Canada, will require at least three. However, no one has ever
been able to find a map for which more than four colors were needed. The
Four Color Problem is to show that no such map exists.
The problem came to light first in 1852, when Francis Guthrie, a stu-
dent at the University of London, posed it to his brother Frederick, who
in turn passed it on to Augustus de Morgan. Evidently, it did the rounds
among mathematicians for a number of years, for in 1878, Arthur Cay-
ley mentioned at a meeting of the London Mathematical Society that he
was unable to solve it. In the following two years, independent “proofs”
were published by P. G. Tait and A. B. Kempe. However, P. J. Heawood
discovered errors in these in 1890, although he did prove a fairly general
result about coloring maps. Interest grew in the problem and it spawned
many new techniques, but a solution eluded an ever-increasing circle of
mathematicians. Eventually, in 1976, a complicated proof of the conjecture
requiring extensive computer resources was found by Haken and Appel.
A survey of map colorings appears in G. Ringel, Map Color Theorems
(Springer, 1974).
In tackling a problem like the Four Color conjecture, it is customary to
reformulate the situation. Represent each region by a node or vertex (you
can think of this as the capital of the region); join two vertices by edges if
and only if their corresponding regions have a boundary line in common.