4 color map theorem?

The four-color theorem states that any map in a plane can be colored using four-colors in such a way that regions sharing a common boundary (other than a single point) do not share the same color.

mathworld.wolfram.com...

I know this has been proved using a computer, but i don't think there has been any easily approachable proof done yet

My stab at it . . . (placing foot in mouth, swallowing hard)
...........................................................................................................................

consider the local case of a single cell,

Imagine we are shrinking the cell down to a point and all the cell's boundary intersections come together at a point.

It is a radial intersection of line segements at a point. (imagine the dividing segments stretching to infinity while we consider the local intersection)

ignoring the cell-point itself for the moment, the maximum number of colors we need, locally, at this intersection is 3 ( 2 if even segments/cells come together, 3 if odd) (with even you just alternate them and if needed use the 3rd for the odd cellpoint)

so we need three non-cell colors & the cell color ( 3 + 1 = 4 )

locally this is true for any cell on the map.

This is true for all cells on the map.

So this is true of the entire map as long as it has cells everywhere and no two cells are occupying the same area on the map.

...........................................................................................................................
(not sure if this is rigorous or thorough enough to be a proof)
any rational, civil, critiques, notes on errors/limitations, or other ideas welcome.

Odd thought,
I believe you can remove all the cells of a single color on a properly 4 colored map by shrinking them down to points and have a properly colored 3 color map.

I will even speculate that you might be able to take another set of the cells of a second color the same way, shrinking to a point and have a viable 2 color map.

nice to be able to attempt this anonymously
.

I can think of a 3D surface where it is not true.
imagine a cell with 4 radial cells,
two opposing radial cells hang down in a loop in 3D and meet one another
the other two opposing radial cells hang down in a lower loop in 3D and meet one another

central cell is yellow, first two opposing radials must be not-yellow1 and not-yellow2
2nd two opposing radials must be not-yellow3 and not-yellow4

requires 5 colors.

now imagine a cell contained in the central cell curving up and out [like a spacewarp wormhole] that loops around and adjacently contacts all those hanging strips, requires 6 colors.

and so on, . . .

with more convolution of a surface in 3D I'm quite sure you could create maps requiring endless numbers of colors. You can connect any cell with as many other cells using wormholes.
.

.
(hope no one minds too much as i chatter to myself here)

I think to define the 4 color map problem I need a good topological definition of what we/I think of as a 2D plane.

I was thinking that 3 sets of points, the plane and the two sets of points it partitions would work. But that would work for something with a wormhole interlocking the two partitioned sets of points.

But i was thinking with a completely flat plane you could fixate/freeze/lock the relative positions [distances?] of all the points of a single partition and rotate them [any amount of rotation] on an axis perpindicular to the set of plane points without disturbing either the plane point set or the other partitioned set of points.
I suppose the plane itself could be included as independantly rotatable.

Actually defining the plane as the necessarily rotatable set of points might make it more efficient. [linear shift might work just as well as rotation]

so i think anything i would/will define as a plane has a one to one correspondence with each of the 3 point sets, the plane and two partitions, all independently rotatable. By using the one to one correspondence it allows for a rippled or distorted plane surface.

That would also work for a sphere, but that seems acceptable to me as a simple 3D space biforcating partition.

if someone has a clear topological definition of a simple flat plane (that hopefully my mind can comprehend) it would be great to see.
.

notes:

1) a single cell is topologically equivalent to a circle

2) i will treat the idea of a planar surface as intuitive and not explicit, the explicit case of convex folding into the 3rd dimension is included in footnotes

mutual adjacency is what requires differentialble colors

cases:

1) unbounded/infinite single cell - one color

2) single cell floating in another cell - two color

3)single cell with two mutually adjacent borders [think of a split plane with a circle floating between the two] requires 3 colors

4)single cell with three mutally adjacent borders [think of a plane split with 3 radial (fat pie slice) regions and a circle that is ontop of the radius point] requires 4 colors

radially this is the maximum number of mutually adjacent cells, if you have 4 radial cells the pairs across from one another are not adjacent. As you increase the number of radial regions/cells the mutual adjacency of all regions is reduced and never increased.

footnotes:

We want to find the case of maximum adjacency on a planar type surface.

imagine a triangle created by 3 adjacent border colors.

wrap this around a sphere (which creates maximum adjacency with convergence on far side of sphere) which topologically equals a 4 color tetrahedron.

we attempt to add a new cell adjacent to all four cells, retaining a convex (sphere-tetrahedron) surface:

there is no way of coloring along the edges of the tetrahedron (attempting to create a new cell) that contacts all the the triangles without isolating one of them from another meaning they are no longer adjacent and therefore no longer required to be different colors.

you can't color down the middle of a triangle [biforcate it] because that creates two cells that are no longer forced to be the same color. (they each become cells isolated from each other)

explict proof you cannot biforcate a triangular region where each of the created regions are adjacent to all three border regions
note: biforcating a triangle with a region is equivalent to biforcating it with a flexible line segment

biforcating a triangle:

topological possibilities, biforcating seg can contact triangle either in mid-segment or at point

think of a flexible wire,

wire endpoints contact the border triangle at 2 places:
1. point - itself (same as a cell floating within a cell)
2. point - adjacent midpoint
3. point - another point
4. point - opposite midpoint
5. midpoint - itself (equivilent to case 1, the cell floating within a cell)
6. midpoint - another midpoint

case for each above (reg=biforcation created region; assume reg1 and reg2 always have contact; border=bordercolor)
1. reg1 contacts no border, reg2 contacts 3 borders (reg1-anything but 4th color, reg2 must be 4th color)
2. reg1 contacts one border, reg2 contacts 3 borders (reg1 non-contact border, reg2 4th color)
3. reg1 contacts one border, reg2 contacts 2 borders (reg1 non-contact border or 4th, reg2 non-contact border or 4th color)
4. reg1 contacts 2 border, reg2 contacts 2 border (reg1 non-contact border or 4th, reg2 non-contact or 4th)
5. (see case 1)
6. reg1 contacts 2 border, reg2 contacts 3 border (reg1 non-contact border, reg2 4th color)

this demonstrates that there is no way of biforcating a triangle where both regions contact all three borders. worst case is 6 with them contacting 2 and 3 border regions.
.

ok this is the ACTUAL PROOF (omg here he goes again)

mutual adjacency is what requires color differentiation.

it is possible to have four cells mutually adjacent on the plane and impossible for 5 or more.

each cell is a vertex
each edge is a an adjacency
each edge/adjacency biforcates between the other edges just like adjacent borders do.
with four points you can draw edges/lines on a plane that connect to each of the other points/cells
it is impossible to do this with 5 [or greater] points staying on the plane.

note: imagine the graph like the bones behind the fleshy cells and borders. operationally they are identical.

if you make an entire map of of vertexes and randomly connecting edges there can be no where on the map that has 5 points all connected together.


This is VERY close to a proof. I think i need to show something else about the map/graph as a whole.

edit:

This is recursively true,
a vertex-cell that has 4 mutual adjacencies can not have more than 4 mutual adjacencies to any other cells with 4 mutual adjacencies themselves. (which is actually redundant) the nesting can be infinite and or partial and the maximum number of mutual dependancies is 4.

The proof has been lying around all this time and no one connected it to the problem.

[edit on 13-4-2005 by slank]

.
Color differentiation is a requirement of mutual adjacencies.

The map is topologically and completely representable with cells as vertexes and adjacencies as edges between vertexes.

The maximum mutually and completely connected set of vertexes is 4.
[this is an old assertion (proof?), many will recognize it]
..................................
expicit proof [which has probably been done many times before]
completely connect a set of points/dots on a piece of paper so ever point connects directly to every other point.
however you twist and stretch it in a plane, topologically this the only and every case of it in a plane. [you may recognize it as a smashed tetrahedron with one side wrapping around infinity] It creates 4 bounded regions.
now we have to drop a new dot in one of the 4 regions created by this completely connected graph such that it can connect with all the other points without crossing any of the other edges. Each region is isolated from one external point. It makes it impossible to do within the plane.
...................................

This means the maximum level of mutally adjacent cells/vertexes/points is 4.

If we take any sections of the graph/map and connect them together the maximum level of mutually adjacent sections is 4.
The entire map will never require more than 4 colors to never have any two adjacent cells the same color.
.

.
Graph representation of Map:

Look at a map.
each cell is bounded by a set of surrounding cells.
only one other cell can be adjacent to that cell for some length of its border
a squiggly line segement.
draw a short hatch mark perpindicular to that squiggly line segment
draw all the hatch marks for a single central cell
put a point inside the central cell
join all the hatchmarks to the point
make a point inside each cell
join all the hatchmarks for each and every cell

viola, you have a graph of vertexes and edges representing your map, with all elements (cells and their radially ordered adjacencies to other specific cells)

You say what if i have a cell or set of cells completely nested in another cell?

from the viewpoint of the cell those still work as adjacencies to the cell at its border.
these are easily represented by branching off the point cell in the 3rd dimension in a plane that is mutually exclusive to the first, with the strict previso that the cell in a planar surface the map works as a boundary between these two sets of cells. These two planes can not connect/meet, not in this 3rd or any other dimension.

Because this potentially additional plane is independent, from here on the argument for one is the argument for the other.
[I think that covers it]

required color differentiation is a function of mutual adjacencies.

To require/force the use of N colors one must have N cells all completely connected to one another. A completely connected graph.

In a plane we can draw a completely connected 4 vertex graph without intersecting edges.
it creates 4 regions.
to draw the 5 point completely connected graph in the plane we must drop a point somewhere (other than existing points/edges) that we can connect to all the other 4 points.
if we drop a point in any of the 4 regions it is isolated (unconnectable) to one point without crossing an edge or intersecting a point.

You say what if there is some other unknown bigger number than 5 points that is completely connectable in the plane?

[certain this must be a theorem somewhere]
If you have some completely connected graph with N vertexes, then if you take any N-1 vertexes each is directly connected to each of the other chosen N-1 vertexes.
So every completely connected graph of size N must contain a completely connected graph of size N-1. In fact there must N of them.

If you cannot create a single completely connected graph of size 5 in the plane, you therefore cannot create a graph of size 6, if not 6 then not 7, and so on . . .

For a single cell it has been shown that 4 is the maximum number of mutually adjacent (completely connected) vertexes/cells.

What about sections of cells?

contiguous section - a set of vertexes that use only the set direct connections (edges) between two of them to connect them as a group and a connection/path can be made from anyone of them to any other through direct connections.

If you have a section of contiguous cells it is essentially inpenatrable. If you put the contiguous section of graph/map on top of a line that splits a plane it is impossible to create line segment that goes from one side of the halfplane to the other (disallowing going through the plane splitting line) through the contiguous section of graph/map that does not intersect a direct edge or vertex of the contiguous section.

The contiguous section of graph/map is in a sense inpenatrable.

What if there is a hole of other stuff ringed by the contiguous section?
It would act as being isolated from the rest of map and impossible to be made adjacent in any way to the rest of the graph/map from the continuous section.
Treated as the cell within a cell, creating its own theoretical independent plane.

since the contiguous section is inpenatrable as far as the entire external section/rest of map is concerned its direct edges can be considered infinitely short, causing all of its vertexes to become a single vertex. If you treat the contiguous section as one this is topologically equivalent. It of course retains the same radial ordering of vertexes/adjacencies that it did as multiple cells/vertexes.

and just as with a single cell/point adjacencies to this new super cell/point from the rest of the graph/map can not cross over one another (a cell can not be adjacent to more than one cell at a single section of its border and a cell cannot transect/biforcate another cell in the plane without turning it into two cells)

So contiguous sections can be considered as super points with multiple connections/adjacencies to other sections/superpoints. [note: a single cell is also a contiguous section]

again draw 4 points on a plane. connect them with multiple parallel paths between them. dropping a 5th point anywhere on the plane. again it is impossible to draw connections to all the other 4 points.

What about a discontiguous section?
A discontiguous section in the plane is two or more sections.

Therefore the maximum number of mutually adjacent contiguous sections [individual cells are also contiguous sections] is 4.

Therefore the maximum number of colors required to color any planar map is 4.

(darn this is work)
.