Some Reflections on the Four Colour Conjecture Part 1

The four colour conjecture has been allegedly resolved by Appel and Haken and others using “computer proofs” which, however, leave a sense of slight doubt in the mind of cautious critics. After the original computer proof was published in 1976 its authors discovered some minor mistakes in the program, but they hastened to say that these glitches were peripheral and did not invalidate the overall result. The fact remains, though, that the normal human response to so much complexity is not quite as re-assuring as an ordinary, lucid, rigorous proof would be. The reflections in this blog look into the $64 question whether a proper non-computer proof might, one day, be discovered.

The first step is to say exactly (i.e. to define) what is the kind of ‘map’ (network) which, it is hoped, will be shown to be necessarily four-colourable.

This is, of course, the network formed when we replace each separate region by a node, and each frontier between regions by a link. (Excluding ‘point contacts’.)  There are well-known ways of colouring a node of order 3 or 4 when it is present in a large given network. This means that nodes of this kind can be removed, and the remaining network —after their removal— will be smaller. After all such nodes have been removed, we are either left with nothing, or with a network containing only nodes of order 5, 6, 7…. (Such a network after the nodes of order 3 and 4 have been removed may be described as ‘fully saturated’.) Incomplete networks are, of course, easier to colour than fully-triangulated networks, so it is fully-triangulated, fully saturated networks with nodes of order 5 or more which pose the essential four-colouring challenge.

It is relatively easy to prove that such a fully-triangulated, fully-saturated target network of n nodes will have 3n-6 links. Each link involves two nodes, one at each end. So the average number of links per node is 6 – 12/n or slightly less than 6. It follows from this that every bona fide colouring target network will have quite a lot of nodes of order 5. These must be present because they are needed to balance the inevitable presence of many nodes of order 6 or more.

In this blog the aim is to define precisely what this body of fully triangulated networks will look like.

The most satisfactory way to prove the four-colouring conjecture would be to find a general-purpose constructive colouring protocol. 

So how ambitious is this quest? The answer is that It is a very difficult challenge. It is, for example, possible to envisage a network containing a large coherent zone where  every node has an order of 1,000,000 + v where v is determined randomly in the range 0 < v < 10,000. The dense complexity of such a giant network shows just how difficult is the quest for a general-purpose constructive colouring protocol likely to be. 

This blog only takes the first step: an over-view of the kind of structures which are implied by the phrase ‘fully triangulated, fully saturated network’. The method used is based on conceptualising how such structures can be constructed.

POINT 1 – The assembly of such a structure can always begin with a node of order 5. (We know that any such structure will contain numerous nodes of order 5. Any one of these can serve as the starting point.) It will of course be the centre (O) of a pentagon of links (“the original 1^st circuit of O”). 

POINT 2 – New ‘triangles’ of nodes can be added, each based on one of the five links surrounding the initial node (O). 

Question: Could one or two of these triangles be omitted? Answer: No, the outer edge of the entire (finally completed) network will necessariiy consist of a circuit with three nodes. This can’t happen at this stage if some sides of the original pentagon are left without triangular extensions.. 

POINT 3 – The five new triangles described in Point 2 will introduce five new nodes. These new nodes are two links away from the original node O, so we may say that their ‘distance’ from O is 2 units.

POINT 4 – Links may now be added, bridging the five gaps between the new nodes. They can be joined up thus forming a second pentagon, also describable as a ‘2^nd circuit’ of nodes (shown as broken lines on Diagram A), OR, alternatively, linear sets of 1, 2, 3 or more links and nodes may be inserted in some or all of the gaps instead (see Diagram B). In the latter case each of the latest new nodes will acquire a link back to a node on the original pentagon, thus completing their triangulation.  NOTE: the numbers here could already be large. There could be a million + 10,000 of these newer extra nodes between each pair of the first set (circuit) of nodes. 

POINT 5 – These extra nodes, taken together, form a new circuit which may be said to be the ‘2^nd’ circuit. These new nodes are  ‘two units’ away from the origin, O.

POINT 6 – There are now two kinds of ‘2nd^’ circuit which may consist of (a) entirely nodes linked only to two nodes of the original pentagon (“the original 2^nd circuit”) or (b), an “enriched 2^nd circuit” containing various extra nodes which are linked back to nodes of the original 1^st circuit.  (See Diagram C)

POINT 7 – The original 2^nd circuit may be said to be ‘completable’ because all the five nodes could be “terminated” —linked to a final node F (See Diagram D: notice that all the nodes here are of order 5) thus forming a fully triangulated network. The second kind of circuit is ‘incompletable’ (=not terminatable at this stage), because some of the nodes would end up having only the order 4.
POINT 8 – This protocol can be continued indefinitely so that we eventually end up with a completable circuit and a final node F. This is the simplest category of network we need to consider.  (There are however other, more complex, kinds of networks which emerge if, at a given stage, links are introduced bridging two different nodes on the same circuit —i.e. two different nodes which must be at least four units away from each other— which are the same distance from O.)

POINT 9 –  It will be shown in the next blog how networks of the simplest kind can be four-coloured. 

CHRISTOPHER ORMELL 1^st OCTOBER 2023

If you would like an online copy of the P E R Narrative Maths Manifesto, send an email to per4group@gmail.com asking for this.