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

 2016-05-23, 05:42 #2 LaurV Romulan Interpreter     Jun 2011 Thailand 22·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 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 172D16 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

23·7·163 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 04:12.

Sat Oct 31 04:12:53 UTC 2020 up 51 days, 1:23, 2 users, load averages: 3.21, 2.72, 2.46