Some Reflections on the Four Colour Conjecture PART 3. A new proof of the Four Colour Conjecture.

The four colour conjecture began as an observation about colouring maps with a palette of only four colours so that every boundary was represented by a change of colour. It soon turned into a mathematical challenge involving fully triangulated networks, the nodes of which could always, apparently, be coloured with a palette of four colours, each link having a different coloured node at each end.

We saw in Part 2 that the idea of “colouring as you go” —which looked at first as if it might be a magic bullet— fails, because alternative ways of closing down any limb of the thicket of bifurcating limbs can throw the entire previous allocation of colours into nonsense.

The obvious way to tackle the problem is, of course, by induction. Unfortunately, though, this commonsense approach has not so far delivered a solution to the problem. The present author has concluded that it is worth trying an “induction plus” approach —that is, starting with an hypothesis aimed to prove a little more than the bald four-colourability of a fully triangulised network of n nodes for any n, where n is a natural number.

Preliminary Lemma 1:  there are well-known ways of removing (‘weeding’) nodes of order 3 and 4 from a fully triangulated network without compromising the colourability of the weeded network. A node of order 3 is linked to the three corners of a triangle, so it can evidently be coloured using the remaining colour not present on that triangle. Thus removing any node of order 3 does not compromise the 4-colourability of the remaining network.

In the case of a node of order 4 we first remove that node and then amalgamate a pair of nodes at opposite corners of the quadrilateral circuit which has been vacated,  Any valid four-colouration of the weeded network will transpose into a valid four-coloration of the original network.

Preliminary lemma 2: After all weedable nodes of order 3 and 4 have been removed, there will be a substantial set of nodes of order 5 present in the network, because the average order of its nodes will be just less than 6. (Actually  6 – 12/n.) If the network only contained nodes of order 6 or more, this average would be an impossibility.

Preliminary lemma 3: Only fully weeded networks need be considered in a proof.  

Preliminary lemma 4: The first fully triangulated, fully weeded network is a network of 12 nodes each of which is a node of order 5.   

CONJCTURE:  Any fully triangulated (plane) network of nodes can be four coloured and in such a way that any nominated pair of ‘semi-adjacent nodes’ —i.e. nodes two links apart separated by a single intermediate node— will be coloured with the same colour. 

PROOF BY INDUCTION  The working hypothesis is that this conjecture is valid for all such networks up to n nodes.

[It is easy to check that this is valid in the case when n=12 and all the nodes are of order 5.]

Now consider any given fully weeded, fully triangulated, upgraded network of n+1 nodes. We shall call this the ‘major network’.

It will contain considerable numbers of nodes of order 5, each surrounded by a pentagonal circuit.

Consider one of these nodes, P, surrounded by a circuit of nodes A, B, C, D and E.

Now remove P and amalgamate nodes A and C to form node X. (See Diagram 4) The result is a lesser, fully triangulated network of n-1 nodes. This will be called the ‘minor network’. (It may or may not be fully weeded.)  

Now the working hypothesis says that this minor network can be four coloured in such a way that B and D have the same colour. Now split X into two nodes A_X and C_X and separate them.  The network now has a hole (an empty pentagonal circuit) surrounded by the five nodes A_X, B, C_X, D, E.  This pentagon of nodes involves only three colours, the colours allocated to X, B & D and E. So the node P can be re-inserted and coloured with the fourth colour, i,e, the colour remaining after the three colours of X, B & D and E have been allocated.

We now have a valid four-colouring of the major network of n+1 nodes.

It remains to show that any nominated pair of semi-adjacent nodes in the major n+1 node network can be coloured with the same colour (within a valid 4-colouring of the whole)..  

Unfortunately we can’t use the extra bit of the original hypothesis on the minor network because that has already been invoked when we allocated the same colour to B and D.

Now reconsider the major network of n+1 nodes with which we started.  It will contain numerous nodes of order 5, so select one of these, Q, different from P. Next, remove Q leaving a pentagon of nodes surrounding an empty space. We know from the previous reasoning that the major network can be four-coloured, so this pentagon will have five nodes, two of which are of colour I, two of which are of colour 2, and one of which (G, the singleton) has the third colour.   We now create a new link between G and the more distant node coloured with I and a new link with the more distant node with colour 2. We now have a lesser network of n nodes which is exactly the same as the major network except that Q has been replaced by two new links. So this new ‘lesser’ network will be colourable with four colours and —because it has only n nodes we can invoke the working hypothesis— so any two of its semi-adjacent nodes can be allocated the same colour. 

This means that most of the semi-adjacent pairs of the major network can be specially allocated the same colour. (=There is a valid 4-colouring of the whole which includes this detail.) The exceptions are the five semi-adjacent pairs whose mid-point is Q and the complete set of semi-adjacent pairs which end in Q. (See Diagram 6) Since Q is no longer there in the lesser network, they cannot be shown to be allocatable with the same colour. This will be called the ‘deficit set of semi-adjacent pairs of nodes’. 

However, we can choose another order-5 node of the major network R which is some distance away from Q and repeat the same process which we applied to Q.  As before, this will not entail that the semi-adjacent pairs around R in the major network can be allocated the same colour (but we don’t need this verification, since it has already been established by the process detailed above), but crucially it will entail that the deficit set of semi-adjacent nodes associated with Q can be allocated the same colour.  

So now we have shown that the hypothesis that any fully triangulated network of n nodes can be four-coloured —with the extra result that any two semi-adjacent nodes can be allocated the same colour (within the overall 4-colouring) — entails that the same thing is true of any network of fully triangulated nodes of n+1 nodes.  As the hypothesis is evidently true when n=12, it follows, by the principle of induction, that it is true for all natural numbers, n.

It follows that the hypothesis is valid for all values of n. QED    

CHRISTOPHER ORMELL 2^nd JANUARY 2024
If you would like an online copy of the P E R Narrative Maths Manifesto, send an email to per4group@gmail.com