A doubt about the correctness of the Four Colour Theorem

Raman · 2016-05-23, 03:07

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 K₅ 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₄ 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 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 5-chromatic, but it has got no K₅ 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 2-chromatic, since it is bipartite, but it is not a planar graph.

LaurV · 2016-05-23, 05:42

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.]

CRGreathouse · 2016-05-23, 18:53

I've highlighted a subgraph which is homeomorphic to K₅.

Batalov · 2016-05-23, 21:15

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 K₅ or K_3,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 K₅ or K_3,3 in it.
CRG showed that in your graph, there is, and LaurV pointed to the same: it is not planar.

Raman · 2016-12-25, 06:55

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₅ or K_3,3 contained in it.
True Statement: A graph is planar if and only if there are no subgraphs homeomorphic to K₅ 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₅ or K_3,3 contained in it.

Statement 2: A graph which has no subgraphs homeomorphic to K₅ 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₅ may be coloured with fewer than 5 colours).
(Or any graph without subgraphs homeomorphic to K₅ 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?

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 K₅ 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₄ 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 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 5-chromatic, but it has got no K₅ 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 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 5²×7×53 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 2·29·103 Posts	I've highlighted a subgraph which is homeomorphic to K₅. Attached Thumbnails

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

2016-12-25, 06:55	#5
Raman Noodles "Mr. Tuch" Dec 2007 Chennai, India 1257₁₀ 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₅ or K_3,3 contained in it. True Statement: A graph is planar if and only if there are no subgraphs homeomorphic to K₅ 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₅ or K_3,3 contained in it. Statement 2: A graph which has no subgraphs homeomorphic to K₅ 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₅ may be coloured with fewer than 5 colours). (Or any graph without subgraphs homeomorphic to K₅ 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?