display | more...

Every map has at least one country with five or fewer neighbours

This theorem is central to any attempted proof of the Four Colour Theorem. It relies on Euler's formula, F-E+V=2, to relate the number of countries, borders and meeting points (defined below). It is normally associated with polyhedra, however, it is possible to project any polyhedron on to a plane. The converse of which, is that it is possible to take a map (on a plane) and construct a polyhedral representation of it - allowing the use of Euler's formula.

The number of countries is equivalent to the faces of the polyhedron, the borders are the edges and the meeting points are the vertices.

A 'meeting point' is defined to be where at least three borders meet. So, for each vertex, there will be at least 3 edges connected to it. However, as each edge is connected to two vertices, the relationship between them can be expressed as:
   E ≥ 3V/2
or equally:
   V ≤ 2E/3

This is a proof by contradiction. We are going to assume that, for any map, there are no countries with less than six neighbours. This translates as there being no face with less than six edges.

So, for each face there are (at least) 6 edges. However, again, each edge borders two faces, so the relationship is:
   E ≥ 6F/2
   E ≥ 3F
or equally:
   F ≤ E/3

Putting these two inequalities into Euler's formula gives the following:
   F - E + V ≤ (E/3) - E + (2E/3)
   F - E + V ≤ 0
but, Euler's formula states:
   F - E + V = 2

This is the contradiction we require to disprove the assumption. Hence, there must be a country with 5 or fewer neighbours.