mersenneforum.org A doubt about the correctness of the Four Colour Theorem
 Register FAQ Search Today's Posts Mark Forums Read

 2016-05-23, 03:07 #1 Raman Noodles     "Mr. Tuch" Dec 2007 Chennai, India 3·419 Posts A doubt about the correctness of the Four Colour Theorem A given graph is 2-chromatic if and only if it is bipartite (i.e., it has no odd length cycles). Determining this can be done in P (i.e., deterministic polynomial time). On the other hand, determining whether a given graph is n-chromatic (i.e., for the given values of n such that where n ≥ 3) is a NP-complete problem. What if we are restricted only to planar graphs?? The four colour theorem states that any given planar graph can be coloured with only four colours on regions with no two adjacent regions sharing the same edge having the same colour. Because of the duality theorem, this statement is also equivalent to saying that any given planar graph can be coloured on vertices with only four colours with no two adjacent vertices joined by some edge having the same colour. The Kuratowski's theorem states that a graph is planar if and only if there are no K5 or K3,3 subgraphs in it. However, a minimum of four colours are needed to colour planar graphs on vertices or on regions, as the following tetrahedral graph K4 shows as follows as: whose adjacency matrix is given by using: 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 Putting things the other way, A graph is n-chromatic if it has no Kn+1 subgraphs in it. This is clearly a false statement. For n = 2, a pentagonal graph is a counterexample. For n = 3, the following graph is a counterexample, whose adjacency matrix is given by using: 0 1 1 0 0 0 1 1 0 1 1 0 0 0 1 1 0 1 0 0 0 0 1 1 0 1 1 0 0 0 0 1 0 1 1 0 0 0 1 1 0 1 1 0 0 0 1 1 0 Question: For n = 4, the following graph is 5-chromatic, but it has got no K5 or K3,3 subgraphs in it. So, if the Kuratowski's Theorem as stated above is not wrong or incomplete, then the Four Colour Theorem is false. Could someone please explain me what I am missing or doing wrong or if possible draw the following graph on a plane without overlapping edges, and then construct its primal or dual with five colours?? Or if the following graph is not planar, please fix the missing or done wrong part of the Kuratowski's Theorem as stated above. For n = 4, the following graph is a counterexample, whose adjacency matrix is given by using: as follows as: 0 1 1 1 0 1 1 1 0 1 0 1 1 1 0 0 0 0 1 1 0 1 1 0 0 0 0 1 1 1 0 1 0 0 0 0 0 1 1 1 0 0 0 0 1 1 0 0 0 0 0 1 1 1 1 0 0 0 0 1 0 1 1 1 0 0 0 0 1 1 0 1 0 0 0 0 1 1 1 1 0 As a note, please notice that it was the Five Colour Theorem which had been proved manually to certainty. The proof of the Four Colour Theorem was computer aided and thus may not be certainly correct. By the way, as a note, please notice that the planarity criterion for any given graph for it to be planar is only a sufficient condition, but not a necessary condition. This is clearly a noticable condition, if one considers the K3,3 graph, which is 2-chromatic, since it is bipartite, but it is not a planar graph.
 2016-05-23, 05:42 #2 LaurV Romulan Interpreter     Jun 2011 Thailand 100100111011002 Posts There are two big confusions going on there. First, not all graphs which can be colored with 4 colors are planar, and the best example is K33. Second, try to draw your graph in a plane. [edit: to be clear, he took two K5, welded them in a corner, then took one edge of each, unsoldered them both from the common vertex only, and welded together the unsoldered ends. The new graph has clearly no K5, and it is not 4-colorable. So, you either have to be unable to draw it in a plane without any edge intersection, or you have to find the hidden K33 subdivision (this aspect is missed by many, they look for a full K33). Otherwise, something is fishy.] Last fiddled with by LaurV on 2016-05-23 at 06:39
 2016-05-23, 18:53 #3 CRGreathouse     Aug 2006 32·5·7·19 Posts I've highlighted a subgraph which is homeomorphic to K5. Attached Thumbnails
2016-05-23, 21:15   #4
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

3×5×17×37 Posts

The error is here:
Quote:
 Originally Posted by Raman The (misquoted) Kuratowski's theorem states that a graph is planar if and only if there are no K5 or K3,3 subgraphs in it. So, if the Kuratowski's Theorem as stated above ...
The Kuratowski's theorem states that a graph is planar if and only if there are no subdivisions of K5 or K3,3 in it.
CRG showed that in your graph, there is, and LaurV pointed to the same: it is not planar.

 2016-12-25, 06:55 #5 Raman Noodles     "Mr. Tuch" Dec 2007 Chennai, India 3×419 Posts Happy December (winter) solstice! It has passed! Today - Merry Christmas! I am not a Christian, but a Hindu, but wishing it to you all anyway! Pardon my late reply, since I had to think about it deeply and then prepare about it. Thanks for all your replies! I have corrected my mistake which I have learnt incorrectly from my college days... from the Graph Theory course! False Statement: A graph is planar if and only if there are no subgraphs of K5 or K3,3 contained in it. True Statement: A graph is planar if and only if there are no subgraphs homeomorphic to K5 or K3,3 contained in it. So, is the four colour conjecture really hard to prove? In my opinion, the Collatz conjecture should not be too hard to prove, either! Does the following proof of the four colour conjecture work out? Why or why not? To prove: Every graph which is planar can be coloured with 4 colours. (Let us assume vertex colouring; due to duality theorem, it is also equivalent to region colouring). Statement 1: Kuratowski's Theorem states that a graph is planar if and only if there are no subgraphs homeomorphic to K5 or K3,3 contained in it. Statement 2: A graph which has no subgraphs homeomorphic to K5 contained in it can be coloured with 4 colours. (Since chromatic number of 5 requires at least 5 vertices each of which are adjacent to each other). (On the other hand, graphs obtained by expanding edges from K5 may be coloured with fewer than 5 colours). (Or any graph without subgraphs homeomorphic to K5 contained in it with that as subgraph). So, Statement 1 and Statement 2 implies that every planar graph is 4-chromatic. Isn't it or isn't it not?

 Similar Threads Thread Thread Starter Forum Replies Last Post wildrabbitt Hardware 1 2015-08-06 05:51 skan Software 16 2013-04-01 16:54 ET_ Software 20 2011-11-18 11:19 Mr. P-1 Puzzles 3 2009-03-03 02:34 Wacky Puzzles 80 2008-11-13 20:08

All times are UTC. The time now is 15:43.

Sun May 16 15:43:47 UTC 2021 up 38 days, 10:24, 1 user, load averages: 2.27, 3.58, 3.76