mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2016-05-23, 03:07   #1
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

3×419 Posts
Default 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.
Raman is offline   Reply With Quote
Old 2016-05-23, 05:42   #2
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22·7·317 Posts
Default

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
LaurV is offline   Reply With Quote
Old 2016-05-23, 18:53   #3
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

172D16 Posts
Default

I've highlighted a subgraph which is homeomorphic to K5.
Attached Thumbnails
Click image for larger version

Name:	graph.png
Views:	115
Size:	4.3 KB
ID:	14421  
CRGreathouse is offline   Reply With Quote
Old 2016-05-23, 21:15   #4
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23·7·163 Posts
Default

The error is here:
Quote:
Originally Posted by Raman View Post
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.
Batalov is offline   Reply With Quote
Old 2016-12-25, 06:55   #5
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

3·419 Posts
Default

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?
Raman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
transformer oil changing colour wildrabbitt Hardware 1 2015-08-06 05:51
doubt with PARI and modular operations skan Software 16 2013-04-01 16:54
Doubt about P-1 algorithm ET_ Software 20 2011-11-18 11:19
The Colour of Money Mr. P-1 Puzzles 3 2009-03-03 02:34
What colour is the bear? 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.