Talk:Five color theorem

Full proofs

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)

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

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)

Linear-time algorithm

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)

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)

alternative (simpler ?) linear 5-coloring algorithm

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)

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)

Euler characteristic

"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)

The Euler characteristic of the plane is 2, so $F+V=E+2$. By assumption the graph has no multiple edges, so each face has at least three sides. Therefore $2E\geq 3F$. Now if every vertex had at least six adjacent edges we would have $2E\geq 6V$, and so

$F+V=E+2={\frac {2E}{3}}+{\frac {2E}{6}}+2\geq F+V+2$

which is impossible. –Henning Makholm (talk) 16:25, 23 October 2010 (UTC)

A picture would help

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)

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

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)

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.
—Ruakh_TALK 17:25, 2 June 2013 (UTC)

Assessment comment

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)

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

Requested move 22 August 2020

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)

---

Five color theorem → Five-color theorem – Punctuation Electricmaster (talk) 08:38, 22 August 2020 (UTC)

• Weak oppose on grounds of article stability. The sources barely seem to refer to this as... anything... in the current article (OR?), but the given rationale is unconvincing - this is a title, not a piece of running text, and thus might not always follow normal punctuation standards. SnowFire (talk) 16:28, 22 August 2020 (UTC)
• Oppose per argument above, that article doesn't necessary always follow normal punctuation rules, but Move to Five colour theorem because more precise. 114.125.232.69 (talk) 16:50, 22 August 2020 (UTC)
  • UK standard spelling is more precise than American standard spelling? How interesting. But see WP:ENGVAR, which your suggestion violates. —David Eppstein (talk) 17:15, 22 August 2020 (UTC)
• Oppose. The title is not ambiguous enough to need hyphenation to resolve an ambiguous grouping. See also the same move request on four color theorem. —David Eppstein (talk) 17:15, 22 August 2020 (UTC)
• Oppose The proposal gives no argument. Both forms are attested in print, but there's no ambiguity that we'd need punctuation to resolve, and the "hyphenate modifiers before the noun" style advice doesn't really apply: the article isn't about a theorem painted in five colors. XOR'easter (talk) 22:41, 22 August 2020 (UTC)
• Oppose because this article not twlling about theorem painted in five colors and should not be hypernated. The correct title of this should be Five colour theorem (with u added). 36.77.142.38 (talk) 23:58, 22 August 2020 (UTC)
• Oppose I speaking a good english i taught in the schools to tell the theorem about five colors as Five colour theorem (with added u) and not Five-color theorem(hypernated). Because it, the actual title for this article should be Five colour theorem. If not moved, please add new description like The five color theorem (known in British, Canadian, Australian, New Zealand as five colour theorem) is a result from graph theory that given a plane separated into regions, such as a political map of the counties of a state, The same statement needs to apply in Four color theorem article. 182.1.31.12 (talk) 00:09, 23 August 2020 (UTC)
  • We don't need to explain a difference between British and American English in every article that uses a word which the two spell differently. XOR'easter (talk) 16:27, 23 August 2020 (UTC)
• Oppose - it's a theorem about five colors, not a theorem being five-color. --CiaPan (talk) 09:32, 23 August 2020 (UTC)
• Oppose hyphenation (and "colour"), per WP:COMMONNAME. Paul August ☎ 14:22, 23 August 2020 (UTC)
• Oppose hyphenation, but move to Five colour theorem as other articles needs to moved to Four colour theorem 110.137.186.235 (talk) 21:07, 23 August 2020 (UTC)
  • I've taken the liberty of striking out all but the first of the Sumatran IPs, on the principle that they're obvious puppetry of some sort (meat or socks, don't care which). —David Eppstein (talk) 22:14, 23 August 2020 (UTC)
• Oppose. Hyphenation is certainly not necessary and can lead to an incorrect interpretation. Absolutely no reason has been given to change to British spelling.--Bill Cherowitzo (talk) 22:11, 23 August 2020 (UTC)

---

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.