There is a nicely presented proof of the Four Color Theorem by Ashay Dharwadker (without any computer help) at the following Yahoo! Geocities Web site:
|FOUR COLOUR THEOREM. For any subdivision of the plane
into non-overlapping regions, it is always possible to mark each of the
regions with one of the numbers 0, 1, 2, 3, in such
a way that no two adjacent regions receive the same number.
STEPS OF THE PROOF: We shall outline the strategy of the new proof given in this paper. In section I on MAP COLOURING, we define maps on the sphere and their proper colouring. For purposes of proper colouring it is equivalent to consider maps on the plane and furthermore, only maps which have exactly three edges meeting at each vertex. Lemma 1 proves the six colour theorem using Euler’s formula, showing that any map on the plane may be properly coloured by using at most six colours. We may then make the following basic definitions.
The easy part of the proof is that the existence of the Steiner system S(N+1,2N,6N) is impossible for N > 4 because of Tit's inequality on the parameters of a Steiner system. A Steiner system S(k,v,t) is an organization of k "points" into v "blocks" such that any t points uniquely determine a block. The easy part of the proof is brief enough to repeat here.
Look up Van Lint and Wilson (A Course in Cominatorics, Cambridge Univ. Press, 1992) reference J. Tits (1964), Sur les systemes de Steiner associes aux trois 'grands' groupes de Mathieu, Rend. Math. e Appl. (5) 23, 166- 184, in regard to the following:
Thm. 19.5 In any nontrivial Steiner system S(t,k,v):
v ³ (t + 1)(k - t + 1)
Proof: A Steiner system S(t,k,v) consists of v "points"
organized into "blocks" (sets) of size k such that any t points uniquely
determines one block containing them. A Steiner system is "trivial" if
k = v (all points in one block) or if k = t (the blocks are simply all
the subsets of size t). Thus a nontrivial Steiner system has more
than one block and k > t. In a nontrivial Steiner system, take t points
from one block and another point not in that block. This is a set
S of t+1 points not contained in any block (since such a block would share
t points with the first block yet be distinct from it by containing the
last point). Now there are t+1 subsets T of S of size t, and each determines
a unique block B(T) containing T. How many points are in the union
over these B(T)? Aside from the t+1 points in S which are surely
covered by this union, consider the points in some B(T) that do not belong
to S. Since there are t points that do belong to S, there must be
exactly k - t points that do not. Further, since distinct blocks B(T),B(T')
share t - 1 points in S through their inclusion of T intersect T' they
cannot share any other points. Thus the size of the union over the
blocks B(T) is: (t+1) points in S + (t+1)(k-t) points not in S. The desired
inequality then follows:
v ³ (t + 1)(k - t + 1)
If we apply this inequality to the Dharwadker's Steiner system S(N+1,2N,6N), it tells us that:
6N ³ (N + 2)N
0 ³ N2 - 4N
This clearly fails for N > 4, so the "easy part" of Dharwadker's proof is easily verified.
The hard part of the idea is to show that a planar map requiring N colors implies the existence of a Steiner system S(N+1,2N,6N). This part of the proof goes far afield in showing the existence of the Steiner system, but it seems well enough written to repay one's study. The lemmas that lead to the conclusion follow logically from the hypotheses. I was able to verify the steps with reference to the group theory texts mentioned in the references. The construction generalizes, what Rotman's book calls, the Witt-Carmichael construction. One important point to note is that all the hypotheses are actually used in the construction. In particular
July 31, 2005