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

On Jun 14, 6:32 pm, Andre <andre.robe...@xxxxxxxxx> wrote:
A few weeks ago, I gave my 15 year old son a book on mathematical
puzzles that included a description of the 4 color theorem. After
spending some time drawing colored maps, he made a connection with
another problem, that of the impossibility of connecting 3 houses with
3 different utilities (gas, water, electricity) without having two
lines crossing.

Graph theory is a fascinating subject, one that I wish I had
more time to explore. There are plenty of unsolved conjectures
in graph theory.

You've got plenty of comments on 4CT (the Four Color Theorem). I'll
comment on your second point, about the houses and utilities.

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.

5CT: Every planar graph is 5-colorable. The proof of this
is much simpler than the proof of 4CT (it was first
accomplished in 1890) and may give you and your son some
insights into elegant graph-theory arguments.

- Randy

.

Relevant Pages

  • Re: [p2p] PNRP Identities and Routing.
    ... to peer graph are constantly evolving, in an attempt to shape the graph ... will be to go ahead and create a direction connection to them. ... As far as I can determine, it is done based on the PNRP ID ...
    (microsoft.public.win32.programmer.networks)
  • Re: Loosing sync with GMFBridge
    ... source graph pauses. ... want (data at sink2 will be discarded if there is no bridge connection). ... Then you can connect the source directly to the renderer, ...
    (microsoft.public.win32.programmer.directx.video)
  • Re: Plusnet Usenet speeds, Official
    ... The graph also doesn't show individuals that remain constant ... just the concurrent number of connection downloading ... 512k connection for 14 hours a day from midday to 2am in the morning. ... Less than 150 customers at any one time during the hours you speak of. ...
    (uk.telecom.broadband)
  • Re: WMP plays mp3, myapp(DShow) doesnt
    ... > GraphEdit won't let me make that connection, ... What graph are you trying to build exactly? ... // Alessandro Angeli ... // a dot angeli at psynet dot net ...
    (microsoft.public.win32.programmer.directx.audio)
  • Re: Some Thoughts on the Four Color Theorem
    ... planar graph which are not planar. ... sometimes called a "separating triangle". ...
    (sci.math)