Jump to content

Talk:Five color theorem

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

Full proofs

[edit]

This is not a proof outline; it is a full proof. Should we really be including entire proofs on Wikipedia? --Wzhao553 06:52, 7 February 2006 (UTC)[reply]

When the full proof is only a couple sentences more than the "outline", who cares? --C S (talk) 05:11, 10 March 2009 (UTC)[reply]

A proof by contradiction should start by stating the proposition that is to be disproved. And a proof that relies on induction usually starts by choosing a minimal counterexample. Here, we could have something like:

We will assume that there exist graphs that cannot be five-colored, and derive a contradiction. If there are such graphs, we choose an example G where the number of vertices is the smallest possible; that is, we assume that all graphs with fewer vertices can be five-colored. Rob625 (talk) 08:12, 26 January 2015 (UTC)[reply]

Linear-time algorithm

[edit]

I added a description of the linear-time algorithm, based on the paper. The mechanics are a little bit complicated, especially the splicing together of adjacency lists during merging, and I hope to clarify this somehow in the future. Deco 00:23, 9 August 2006 (UTC)[reply]

It occurs to me that I'm not entirely sure if this algorithm is relevant to the five color theorem, although it's certainly relevant to five coloring of graphs. Maybe we should consider a move. Deco 00:25, 9 August 2006 (UTC)[reply]

alternative (simpler ?) linear 5-coloring algorithm

[edit]

Hi Deco (?),

Maybe I have alternative algorithm for 5-coloring of simple planar graph, entirely different approach and probably simpler.

Actually, I designed that algoritm a few years ago but I prefered to examine its implication on 4-coloring (seems it has no such implication).

I think I had the source paper for your (modified ?) algorithm somewhere inmy computer backups but I cannot find it. Trying now to access this paper from on-line ACM ( ?) magazine I'm asked for a password or something like this (which I have not). Can you pass me the file of that source paper ?

Before presenting my algorithm (and carefully re-check it), I would like to know wether this is the _only_ linear time algorithm (for 5-coloring of simple planar graph).

a212.150.100.44 212.150.100.44 19:25, 3 August 2007 (UTC)[reply]

This article (or talk page) would be an inappropriate place to present your algorithm due to our Wikipedia:No original research policy, but if you have found a simpler 5-coloring algorithm I definitely encourage you to get some people in the area to look at it for possible publication. I unfortunately can't send you a copy of the publication as this would subvert ACM's exclusive distribution rights, but you might try contacting one of the original authors. Dcoetzee 02:54, 4 August 2007 (UTC)[reply]

Euler characteristic

[edit]

"The proof relies on the Euler characteristic to show that there must be a vertex V shared by at most five edges" Can anyone explain how this follows? Plugwash (talk) 03:18, 20 April 2010 (UTC)[reply]

The Euler characteristic of the plane is 2, so . By assumption the graph has no multiple edges, so each face has at least three sides. Therefore . Now if every vertex had at least six adjacent edges we would have , and so
which is impossible. –Henning Makholm (talk) 16:25, 23 October 2010 (UTC)[reply]

A picture would help

[edit]

This is commonly taught in intro discrete courses (at least from my experience), almost always with the same distinct picture of a node and its 4 neighbours, and the various linkage possibilities between its neighbours. It makes the proof extremely clear, and if the page featured it it'd be even more accessible to people who are introduced to the theorem for the first time. So just a thought: maybe add a picture. Otherwise, when I'm not busy I might make one later. 142.157.58.177 (talk) 02:24, 2 March 2011 (UTC)[reply]

Why doesn't the 5-colour proof work for 4 colours?

[edit]

At a certain point in the proof, we stop mentioning the 5th colour. What difference does it make? Why does the proof need colour #5? --Doradus (talk) 00:49, 1 October 2012 (UTC)[reply]

The proof depends on the fact that every planar graph has at least one vertex with only five neighbors. The corresponding statement with "four" instead of "five" is not true — it's possible to construct a planar graph where each vertex has five neighbors — so a hypothetical corresponding four-color proof would not work.
I've now rewritten the relevant paragraph in a way that hopefully makes it more clear what's going on there.
RuakhTALK 17:25, 2 June 2013 (UTC)[reply]

Assessment comment

[edit]

The comment(s) below were originally left at Talk:Five color theorem/Comments, and are posted here for posterity. Following several discussions in past years, these subpages are now deprecated. The comments may be irrelevant or outdated; if so, please feel free to remove this section.

Really needs diagrams; needs a less technical overview. Tompw (talk) I believe that the link to John Koch points to a "different" John Koch -- which is an artist, not the algorithmist referred to. —Preceding unsigned comment added by 143.106.24.23 (talk) 14:15, 1 November 2007 (UTC)[reply]

Last edited at 14:17, 1 November 2007 (UTC). Substituted at 02:06, 5 May 2016 (UTC)

New name

[edit]

Requested move 22 August 2020

[edit]
The following is a closed discussion of a requested move. Please do not modify it. Subsequent comments should be made in a new section on the talk page. Editors desiring to contest the closing decision should consider a move review after discussing it on the closer's talk page. No further edits should be made to this discussion.

The result of the move request was: not moved. (closed by non-admin page mover) Jerm (talk) 03:23, 30 August 2020 (UTC)[reply]


Five color theoremFive-color theorem – Punctuation Electricmaster (talk) 08:38, 22 August 2020 (UTC)[reply]


The discussion above is closed. Please do not modify it. Subsequent comments should be made on the appropriate discussion page. No further edits should be made to this discussion.