APPENDIX - TOPOLOGY - What Is Mathematics? An Elementary Approach to Ideas and Methods, 2nd Edition (1996)

What Is Mathematics? An Elementary Approach to Ideas and Methods, 2nd Edition (1996)

CHAPTER V. TOPOLOGY

APPENDIX

*1. The Five Color Theorem

On the basis of Euler’s formula, we can prove that every map on the sphere can be properly colored by using at most five different colors. (According to p. 247, a map is regarded as properly colored if no two regions having a whole segment of their boundaries in common receive the same color.) We shall confine ourselves to maps whose regions are bounded by simple closed polygons composed of circular arcs. We may also suppose that exactly three arcs meet at each vertex; such a map will be called regular. For if we replace every vertex at which more than three arcs meet by a small circle, and join the interior of each such circle to one of the regions meeting at the vertex, we obtain a new map in which the multiple vertices are replaced by a number of triple vertices. The new map will contain the same number of regions as the original map. If this new map, which is regular, can be properly colored with five colors, then by shrinking the circles down to points we shall have the desired coloring of the original map. Thus it suffices to prove that any regular map on the sphere can be colored with five colors.

First we show that every regular map must contain at least one polygon with fewer than six sides. Denote by Fn the number of regions of n sides in a regular map; then, if F denotes the total number of regions,

(1)    F = F2 + F3 + F4 + · · ·.

Each arc has two ends, and three arcs end at each vertex. Hence, if E denotes the number of arcs in the map, and V the number of vertices,

(2)    2E = 3V.

Furthermore, a region bounded by n arcs has n vertices, and each vertex belongs to three regions, so that

(3)    2E = 3V = 2F2 + 3F3 + 4F4 + · · ·.

By Euler’s formula, we have

VE + F = 2, or 6V – 6E + 6F = 12.

From (2), we see that 6V = 4E, so that 6F – 2E = 12.

Hence, from (1) and (3),

6(F2 + F3 + F4 + · · ·) – (2F2 + 3F3 + 4F4 + · · ·) = 12,

or

(6 – 2)F2 + (6 – 3)F3 + (6 – 4)F4 + (6 – 5)F5 + (6 – 6)F6 + (6 – 7)F7 + · · · = 12.

Hence at least one of the terms on the left must be positive, so that at least one of the numbers F2, F3, F4, F5 is positive, as we wished to show.

Now to prove the five color theorem. Let M be any regular map on the sphere with n regions in all. We know that at least one of these regions has fewer than six sides.

Case 1. M contains a region A with 2, 3, or 4 sides. In this case, remove the boundary between A and one of the regions adjoining it. (If A has 4 sides, one region may come around and touch two nonadjacent sides of A. In this case, by the Jordan curve theorem, the regions touching the other two sides of A will be distinct, and we remove the boundary between A and one of the latter regions.)

image

Fig. 146.

The resulting map M′ will be a regular map with n – 1 regions. If M′ can be properly colored with 5 colors, so can M. For since at most four regions of M adjoin A, we can always find a fifth color for A.

Case 2. M contains a region A with five sides. Consider the five regions adjoining A, and call them B, C, D, E, and F. We can always find a pair among these which do not touch each other; for if, say, B and D touch, they will prevent C from touching either E or F, since any path leading from C to E or F will have to go through at least one of the regions A, B, and D (Fig. 147). (It is clear that this fact, too, depends essentially on the Jordan curve theorem, which holds for the plane or sphere. It is not true on the torus, for example.) We may therefore assume, say, that C and Fdo not touch. We remove the sides of A

image

Fig. 147.

adjoining C and F, forming a new map M′ with n – 2 regions, which is also regular. If the new map can be properly colored with five colors, then so can the original map M. For when the boundaries are restored, A will be in contact with no more than four different colors, since C and F have the same color, and we can therefore find a fifth color for A.

Thus in either case if M is a regular map with n regions, we can construct a new regular map M’ having n – 1 or n – 2 regions, and such that if M′ can be colored with five colors, so can M. This process may again be applied to M’ etc., and leads to a sequence of maps derived from M:

M, M′, M″, · · ·.

Since the number of regions in the maps of this sequence steadily decreases, we must finally arrive at a map with five or fewer regions. Such a map can always be colored with at most five colors. Hence, returning step by step to M, we see that M itself can be colored with five colors. This completes the proof. Note that this proof is constructive, in that it gives a perfectly practicable, although wearisome, method of actually coloring any map with n regions in a finite number of steps.

2. The Jordan Curve Theorem for Polygons

The Jordan curve theorem states that any simple closed curve C divides the points of the plane not on C into two distinct domains (with no points in common) of which C is the common boundary. We shall give a proof of this theorem for the case where C is a closed polygon P.

We shall show that the points of the plane not on P fall into two classes, A and B, such that any two points of the same class can be joined by a polygonal path which does not cross P, while any path joining a point of A to a point of B must cross P. The class A will form the “outside” of the polygon, while the class B will form the “inside.”

We begin the proof by choosing a fixed direction in the plane, not parallel to any of the sides of P. Since P has but a finite number of sides, this is always possible. We now define the classes A and B as follows:

The point p belongs to A if the ray through p in the fixed direction intersects P in an even number, 0, 2, 4, 6, · · ·, of points. The point p belongs to B if the ray through p in the fixed direction intersects P in an odd number, 1, 3, 5, · · ·, of points.

With regard to rays that intersect P at vertices, we shall not count an intersection at a vertex where both edges of P meeting at the vertex are on the same side of the ray, but we shall count an intersection at a vertex where the two edges are on opposite sides of the ray. We shall say that two points p and q have the same “parity” if they belong to the same class, A or B.

image

Fig. 148. Counting intersections.

First we observe that all the points on any line segment not intersecting P have the same parity. For the parity of a point p moving along such a segment can only change when the ray in the fixed direction through p passes through a vertex of P, and in neither of the two possible cases will the parity actually change, because of the agreement made in the preceding paragraph. From this it follows that if any point p1 of A is joined to a point p2 of B by a polygonal path, then this path must intersect P, for otherwise the parity of all the points of the path, and in particular of p1 and p2, would be the same. Moreover, we can show that any two points of the same class, A or B, can be joined by a polygonal path which does not intersect P. Call the two points p and q. If the straight segment pq joining p to q does not intersect P it is the desired path. Otherwise, let p’ be the first point of intersection of this segment with P, and let q’ be the last such point (Fig. 149). Construct the path starting from p along the segment pp’, then turning off just before p’ and following along P until P returns to pq at q’. If we can prove that this path will intersect pq between q’ andq, rather than between p’ and q’, then the path may be continued to q along q’q without intersecting P. It is clear that any two points r and s near enough to each other, but on opposite sides of some segment of P, must have different parity, for the ray through r will intersect P in one more point than will the ray through s. Thus we see that the parity changes as we cross the point q’ along the segment pq. It follows that the dotted path crosses pq between q’ and q, since p and q (and hence every point on the dotted path) have the same parity.

image

Fig. 149.

This completes the proof of the Jordan curve theorem for the case of a polygon P. The “outside” of P may now be identified as the class A, since if we travel far enough along any ray in the fixed direction we shall come to a point beyond which there will be no intersection with P, so that all such points have parity 0, and hence belong to A. This leaves the “inside” of P identified with the class B. No matter how twisted the simple closed polygon P, we can always determine whether a given point p of the plane is inside or outside P by drawing a ray and counting the number of intersections of the ray with P. If this number is odd, then the point p is imprisoned within P, and cannot escape without crossing P at some point. If the number is even, then the point p is outside P. (Try this for Figure 128.)

*One may also prove the Jordan curve theorem for polygons in the following way: Define the order of a point po with respect to any closed curve C which does not pass through po as the net number of complete revolutions made by an arrow joining po to a moving point p on the curve asp traverses the curve once. Let

A = all points po not on P and with even order with respect to P,

B = all points po not on P and with odd order with respect to P.

Then A and B, thus defined, form the outside and inside of P respectively. The carrying out of the details of this proof is left as an exercise.

**3. The Fundamental Theorem of Algebra

The “fundamental theorem of algebra” states that if

(1)  f(z) = zn + an-1zn-1 + an-2zn-2 + · · · + a1z + a0,

where n ≥ 1, and an−1, an−2, · · ·, a0 are any complex numbers, then there exists a complex number α such that f(α) = 0. In other words, in the field of complex numbers every polynomial equation has a root. (On p. 102 we drew the conclusion that f(z) can be factored into n linear factors:

f(z) = (z – α1)(z – α2) · · · (z – αn),

where α1, α2, · · ·, αn are the zeros of f(z).) It is remarkable that this theorem can be proved by considerations of a topological character, related to those used in proving the Brouwer fixed point theorem.

The reader will recall that a complex number is a symbol x + yi, where x and y are real numbers and i has the property that i2 = – 1. The complex number x + yi may be represented by the point in the plane whose coördinates with respect to a pair of perpendicular axes are x, y. If we introduce polar coördinates in this plane, taking the origin and the positive direction of the x-axis as pole and prime direction respectively, we may write

z = x + yi = r (cos θ + i sin θ),

where image. It follows from De Moivre’s formula that

zn = rn (cos + i sin ).

(See p. 96.) Thus, if we allow the complex number z to describe a circle of radius r about the origin, zn will describe n complete times a circle of radius rn as z describes its circle once. We also recall that r, the modulus of z, written |z|, gives the distance of z from O, and that if z′ = x′ + iy′, then |zz′| is the distance between z and z′. With these preliminaries we may proceed to the proof of the theorem.

Let us suppose that the polynomial (1) has no root, so that for every complex number z

f(z) ≠ 0.

On this assumption, if we now allow z to describe any closed curve in the x, y-plane, f(z) will describe a closed curve Γ which never passes through the origin (Fig. 150). We may, therefore, define the order of the origin O with respect to the function f(z) for any closed curve C as the net number of complete revolutions made by an arrow joining O to a point on the curve Γ traced out by the point representing f(z) as z traces out the curve C. As the curve C we shall take a circle with O as center and with radius t, and we define the function φ(t) to be the order of O with respect to the function f(z) for the circle about O with radius t. Clearly φ(0) = 0, since a circle with radius 0 is a single point, and the curve Γ reduces to the point f(0) ≠ O. We shall show in the next paragraph that φ(t) = n for large values of t. But the order φ(t) depends continuously on t, since f(z) is a continuous function of z. Hence we shall have a contradiction, for the function φ(t) can assume only integral values and therefore cannot pass continuously from the value 0 to the value n.

image

Fig. 150. Proof of fundamental theorem of algebra.

It remains only to show that φ(t) = n for large values of t. We observe that on a circle of radius z = t so large that

t > 1 and t > |a0| + |a1| + · · · + |an-1|,

we have the inequality

image

Since the expression on the left is the distance between the two points zn and f(z), while the last expression on the right is the distance of the point zn from the origin, we see that the straight line segment joining the two points f(z) and zn cannot pass through the origin so long as z is on the circle of radius t about the origin. This being so, we may continuously deform the curve traced out by f(z) into the curve traced out by zn without ever passing through the origin, simply by pushing each point f(z) along the segment joining it to zn. Since the order of the origin will vary continuously and can assume only integral values during this deformation, it must be the same for both curves. Since the order for zn is n, the order for f(z) must also be n. This completes the proof.