Re: Four color theorem: why this is not a proof and pointer to simple explanations

In article <1182168598.035576.16360@xxxxxxxxxxxxxxxxxxxxxxxxxxx>,
Randy Poe <poespam-trap@xxxxxxxxx> wrote:

Formally, the impossibility of solving that problem is this theorem:
"K3,3 is nonplanar". K3,3 is the graph that consists of two sets
of 3 nodes, with every node in the first set connected to every
node in the second set. It is nonplanar, meaning there is no
way to draw it in the plane without lines crossing.

A similar theorem: K5 is nonplanar. K5 is the fully-connected
graph of five nodes, with every node connected to every
other node.

Some more interesting related theorems:

K5-e and K3,3-e are planar for any e. (Take out any single
line and the remaining graph can be drawn in the plane).

A graph is planar if and only if it doesn't contain either
K5 or K3,3.

Although one has to take some care in how one defines
"contain".

--
Gerry Myerson (gerry@xxxxxxxxxxxxxxx) (i -> u for email)
.

Relevant Pages
Quantcast