4-colours theorem can be proved visually

In summary, the 4-colour theorem states that the maximum number of colours required to paint a map is 4. The proof involves exhaustive computation with the help of a computer. However, there is a visual way to prove the theorem by representing the map as a graph where each region corresponds to a vertex and adjacent regions are connected by an edge. It is shown that if there are 5 adjacent regions in the map, it would be isomorphic to a planar graph of K5, which contradicts Kuratowski's theorem. Therefore, the maximum number of required colours must be 4.
  • #1
Adel Makram
635
15
TL;DR Summary
Visual proof of the 4-colour theorem.
The 4-colour theorem states that the maximum number of colours required to paint a map is 4.
The proof requires exhaustive computation with a help of a computer.

But I thought that one can visually prove the theorem in the following way;

If one replaces the map with a graph where each region with a different colour is represented by a vertex and the two adjacent regions represented by an edge between the vertices. Then, the maximum number of vertices in any complete planar local graph where every two vertices are connected and no crossing of the edges is allowed must be 4.
8KywHDxOSJRYSf4eYN2mo0MVqKTMfqmz6SXJWuyrvS5PxqiCHA.png

For example, the picture on the right shows that all vertices (a,b,c,d) are connected and therefore corresponds to the fact that the maximum number of allowed colours is 4.
While the picture on the left shows that it is impossible to get 5 colours to paint the map because the regions represented by the vertices (a) and (d) in the map will not be adjacent to each other (no edge connects (a) and (d) exits without crossing the other edges).
 
Mathematics news on Phys.org
  • #2
The theorem is a lot deeper than that. If you take blocks of four nodes that you have painted, and then got connect all of them to make a larger graph, how do you know you can do that without being forced to connect two nodes that you already painted the same color?
 
  • Like
Likes Adel Makram and Vanadium 50
  • #3
IBTL.

It's not clear what you proved, since you haven't expressed it in the language of proofs, but it appears that you have found one possibility that requires four colors. That's a very different thing than proving the theorem.
 
Last edited:
  • Like
Likes DaveE
  • #4
You have only (somewhat) shown that you don't need 5 colors for maps with 5 regions/vertices (mathematically: because the complete graph K_5 is not planar, i.e. can't correspond to a map). You haven't shown that this applies to arbitrarily large maps. They won't be complete graphs, obviously, but you can create graphs where every vertex has at least four connections, so you cannot easily remove one vertex from consideration.

If it would be that simple people wouldn't have needed a computer...
 
  • #5
Office_Shredder said:
The theorem is a lot deeper than that. If you take blocks of four nodes that you have painted, and then got connect all of them to make a larger graph, how do you know you can do that without being forced to connect two nodes that you already painted the same color?
Because colouring a map requires only local rules, I believe. When this set of 4-nodes becomes part of a larger graph, one can treat each local set of 4-nodes separately without affecting other remote parts of the graph.
 
  • #6
You need to prove that... (if it is correct at all, which I doubt).
 
  • #7
mfb said:
You need to prove that... (if it is correct at all, which I doubt).
Do I need to prove that colouring a map requires local rule?
What I am trying to say is if the 4-colours theorem is false, then the maximum number of required colours should be at least 5. But the picture shows that can not be the case, therefore the theorem must be true.
 
  • #8
What does "local rules" mean?

If I just show you 4 vertices at a time, do you think you can pick colors of those vertices such that at the end you have properly colored the graph? I don't think you can, and am happy to go through an example with you.
 
  • Like
Likes suremarc
  • #9
Adel Makram said:
Do I need to prove that colouring a map requires local rule?

You need to prove something, as in write a proof. Not just make the assertion again and again.
 
  • #10
Office_Shredder said:
What does "local rules" mean?

If I just show you 4 vertices at a time, do you think you can pick colors of those vertices such that at the end you have properly colored the graph? I don't think you can, and am happy to go through an example with you.
Instead, can you show me a part of any graph where the maximum number of distinct colors of the adjacent vertices is 5?
 
  • #11
Adel Makram said:
Instead, can you show me a part of any graph where the maximum number of distinct colors of the adjacent vertices is 5?

Irrelevant. That you have one graph that can be colored with four colors does not prove the Four-Color Theorem.

You have proven nothing whatever. For the third time, I request that you use the language of proofs - a step-by-step logical argument, with lemmas if necessary. I am beginning to doubt that you can even correctly state the Four-Color Theorem, because if you have proven anything at all (which I don't think you have), the Four-Color Theorem isn't it.
 
  • Like
Likes phinds
  • #12
I think that maybe reading about how mathematical proofs work would be the best step to understanding that what you offered in your initial proof is not really a mathematical proof.
 
  • #13
Adel Makram said:
What I am trying to say is if the 4-colours theorem is false, then the maximum number of required colours should be at least 5.
That is trivial as 5 is the smallest integer larger than 4.
Adel Makram said:
But the picture shows that can not be the case
It doesn't do that. It just shows that one specific map is not a counterexample.
 
  • #14
I will try here to put it in a semiformal way;

The map of regions n is isomorphic to a graph of vertices n where each region of distinct colour is represented by a vertex of a different colour.

Adjcaney: two regions in the map are adjacent if there is an edge connecting the corresponding 2 vertices representing these regions on the map.

The minimum requirement: We are trying to colour the map with a minimum number of colors such that no adjacent regions have the same colours.

Suppose that we locate 5 regions in the map which are adjacent and satisfying the minimum requirement.

Then that region is isomorphic to a planar graph of K5.

But Kuratowski's theorem states that a finite graph is planar if and only if it does not contain a subgraph that is homeomorphic to K5

This contradicts the proposal that we can find that a patch of the map with adjacent regions of 5 different colours.
 
  • #15
You are still missing the point. You can have for example a graph of 8 vertices such that any five vertices can be colored with four colors, but you can't combine all the colorings of the 5 vertex sections in a consistent way (there are 56 of them!)

Do you think that if I give you a graph and only show you chunks of five vertices at a time, that you can correctly color the whole graph?
 
  • Like
Likes suremarc
  • #16
Office_Shredder said:
You are still missing the point. You can have for example a graph of 8 vertices such that any five vertices can be colored with four colors, but you can't combine all the colorings of the 5 vertex sections in a consistent way (there are 56 of them!)

Do you think that if I give you a graph and only show you chunks of five vertices at a time, that you can correctly color the whole graph?
You can give me any map with any number of regions, but I think when 5 colors can not satisfy the minimum requirement mentioned above at any subgraph then this is equivalent to the 4 colors theorem.

Or put it in this way; there is no subgraph that requires 5 colors across the entire graph.

If there is no local patch of the graph requiring 5 colors (guaranteed by Kuratowski's theorem), then the entire graph does not require it either.
 
  • #17
I think I just now understood what you meant by coloring. When I say 5 colors, I mean those particular 5 colors; say (red, green, blue, yellow, orange).
Suppose we have a scanning device that walks across the map and is programmed such that it will beep when it finds a region of the map homeomorphic to K5. I claim that we will never hear the beep.
 
  • #18
Adel Makram said:
Suppose that we locate 5 regions in the map which are adjacent and satisfying the minimum requirement.

Then that region is isomorphic to a planar graph of K5.

But Kuratowski's theorem states that a finite graph is planar if and only if it does not contain a subgraph that is homeomorphic to K5

This contradicts the proposal that we can find that a patch of the map with adjacent regions of 5 different colors.
Note that if you have to prove that A implies C, and you at first prove A implies B and then B implies C,
and someone produces a counterexample where B is true, but C is false, then your proof must be wrong.

Here A is: the graph G is planar.
B: the graph G does not contain K5
C: the graph G can be colored with 4 colors.

Now for the counterexample. There are maps that do not even contain a triangle, that need an arbitrary number of colors. Of course these are non-planar.
These are Mycielsky graphs: https://en.wikipedia.org/wiki/Mycielskian
For every graph G with N vertices and E edges, Mycielsky defines a graph with 2N+1 vertices and 3E+N edges that has G as a subgraph, but contains no new triangles, and needs one more color.
If your starting graph has no triangles, your new graph also will contain no triangles.

If you start with a graph with 2 vertices and one edge and use the process 3 times, you get a graph with 23 vertices and 71 edges that needs 5 colours.

There's an image at page 48 of this paper
http://webdocs.cs.uAlberta.ca/~hayward/theses/erik.pdf/
 
  • Like
Likes mfb
  • #19
willem2 said:
Note that if you have to prove that A implies C, and you at first prove A implies B and then B implies C,
and someone produces a counterexample where B is true, but C is false, then your proof must be wrong.

Here A is: the graph G is planar.
B: the graph G does not contain K5
C: the graph G can be colored with 4 colors.
Interesting graphs thank you.

Do you mean a Planar graph G that contains no K5 can be colored with a minimum of more than 4 colors?
 
  • #20
No, the claim is simply that no ##K^5## is not enough to prove that you can do it in four colors.
 
  • #21
Adel Makram said:
Suppose that we locate 5 regions in the map which are adjacent and satisfying the minimum requirement.
The "minimum requirement" applies to the whole graph, not just 5 regions. The minimum for a given subgraph can be smaller. That's trivial.
 
  • #22
Probably the best example is you might guess something like, if a graph has no triangles then it can be colored with 2 colors, because every set of 3 vertices can be colored correctly. But if you just take the graph that's shaped like a pentagon, you can't actually color it using two colors. Any odd numbered cycle cannot be colored with only two colors - so coloring with two colors is not something you can do with a "local rule"

If it's not obvious after that what we are trying to say, I'm not really sure how else to say it. But you should probably at least feel like you're probably wrong, since generations of professionals were all aware of the relationship between ##K^5## graphs and being planar, and none of them thought that was a proof. So please, instead of asking us to explain from scratch again why you haven't proven it, take the time to try to understand the posts already explaining why it's not a proof, and if a specific thing confuses you ask about that.
 
  • Like
Likes pbuk, mfb, Infrared and 2 others

1. How does the 4-colours theorem relate to visual proofs?

The 4-colours theorem is a mathematical theorem that states that any map can be coloured with four or fewer colours in such a way that no two adjacent regions have the same colour. This theorem can be proved visually by creating a map and using different colours to show that four or fewer colours are enough to colour the map without any adjacent regions having the same colour.

2. What is a visual proof?

A visual proof is a way of proving a mathematical theorem using visual aids such as diagrams, pictures, or animations. It allows for a more intuitive understanding of the theorem and can be easier to follow compared to traditional algebraic proofs.

3. Why is the 4-colours theorem considered a difficult problem to solve?

The 4-colours theorem was first proposed in 1852 and was only officially proved in 1976. It was considered a difficult problem because it required a lot of time and effort to find a complete proof. Many mathematicians attempted to prove the theorem over the years, but it wasn't until the advent of computers and advanced algorithms that a complete proof was finally found.

4. Can the 4-colours theorem be proved using traditional algebraic methods?

Yes, the 4-colours theorem can be proved using traditional algebraic methods. In fact, the first proof of the theorem in 1976 was a traditional algebraic proof. However, as mentioned earlier, visual proofs can provide a more intuitive understanding of the theorem and can be easier to follow.

5. How does the 4-colours theorem have practical applications?

The 4-colours theorem has practical applications in cartography, computer science, and even art. It can be used to create maps with minimal colours, which can save printing costs and make maps easier to read. In computer science, the theorem is used in graph theory and can help with designing efficient computer algorithms. In art, the theorem has inspired many artists to create visually appealing and mathematically accurate pieces.

Similar threads

  • General Math
Replies
8
Views
1K
Replies
2
Views
176
Replies
2
Views
670
Replies
1
Views
1K
Replies
1
Views
902
Replies
7
Views
2K
Replies
13
Views
1K
Replies
1
Views
2K
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
Back
Top