20160523, 03:07  #1 
Noodles
"Mr. Tuch"
Dec 2007
Chennai, India
3×419 Posts 
A doubt about the correctness of the Four Colour Theorem
A given graph is 2chromatic 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 nchromatic (i.e., for the given values of n such that where n ≥ 3) is a NPcomplete 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 K_{5} or K_{3,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 K_{4} 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 nchromatic if it has no K_{n+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 5chromatic, but it has got no K_{5} or K_{3,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 K_{3,3} graph, which is 2chromatic, since it is bipartite, but it is not a planar graph. 
20160523, 05:42  #2 
Romulan Interpreter
Jun 2011
Thailand
2^{2}·7·317 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 4colorable. 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 20160523 at 06:39 
20160523, 18:53  #3 
Aug 2006
172D_{16} Posts 
I've highlighted a subgraph which is homeomorphic to K_{5}.

20160523, 21:15  #4  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2^{3}·7·163 Posts 
The error is here:
Quote:
CRG showed that in your graph, there is, and LaurV pointed to the same: it is not planar. 

20161225, 06:55  #5 
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 K_{5} or K_{3,3} contained in it. True Statement: A graph is planar if and only if there are no subgraphs homeomorphic to K_{5} or K_{3,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 K_{5} or K_{3,3} contained in it. Statement 2: A graph which has no subgraphs homeomorphic to K_{5} 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 K_{5} may be coloured with fewer than 5 colours). (Or any graph without subgraphs homeomorphic to K_{5} contained in it with that as subgraph). So, Statement 1 and Statement 2 implies that every planar graph is 4chromatic. Isn't it or isn't it not? 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
transformer oil changing colour  wildrabbitt  Hardware  1  20150806 05:51 
doubt with PARI and modular operations  skan  Software  16  20130401 16:54 
Doubt about P1 algorithm  ET_  Software  20  20111118 11:19 
The Colour of Money  Mr. P1  Puzzles  3  20090303 02:34 
What colour is the bear?  Wacky  Puzzles  80  20081113 20:08 