To learn more, read the article on the Quanta Magazine website www.quantamagazine.org/only-computers-can-solve-this-map-coloring-problem-from-the-1800s-20230329/

I once attended a talk on the four colour theorem. The professor explained the history of the problem and gave the proof of the five colour theorem. He then told us that if we now tried to prove the four colour theorem at home, we would find a proof and it would be wrong. Sure enough, when I tried to adapt the proof of the five colour theorem to prove the four colour theorem I succeeded quite quickly, and it took me considerably longer to realise where the subtle mistake was. (And I only found the mistake because I KNEW that there was one.)

@Mateus_py

9 ай бұрын

Yess this gives me same sensation as the konigsberg bridge problem, aways having the feeling that you can do it! but you also know that is impossible XD

@_FFFFFF_

8 ай бұрын

With my rough back of the napkin math, 1000 hours of 1970s computer time , on a modern smartphone would take appropriate 2 hours, even with poor algorithm search. If an exhaustive search was done then, why would it be invalid now?

@ronald3836

8 ай бұрын

@@_FFFFFF_ the 1970 computer-assisted proof is valid, the method that was used in the 1800s to "prove" the 4-colour theorem can be used to prove that 5 colours suffice, but it very subtly goes wrong for 4 colours. I think the method works by assuming N colours are not enough, taking a minimal map that needs N+1 colours, then finding chains of countries in alternating colours and showing that you can flip them in such a way that you free up a colour for the country that needed the N+1-th colour. So contradiction, which means you have shown that N are enough. So with N=5 you can make this work (and you can explain it to a high school student), and with N=4 it almost works but not quite.

@tasty_fish

7 ай бұрын

How do you deal with multiple enclaves?

@ronald3836

7 ай бұрын

@@tasty_fish The four/five colour theorem ignores them.

0:43 Holding down a map with solids of constant width - I like this guy already.

@Will.i.am.Mitchell

9 ай бұрын

😂

As a mapmaker, I never expected this to be an actual discussion in math! I’ve had to deal with the 4/5 color theories before when making state maps or county maps. but I never considered the math behind it!

@idk_whatmynameis

7 ай бұрын

Samee

@leoglisic8324

4 ай бұрын

@@spltorky colors can repeat. You can even have ten countries touching one country (call it X), you just reuse three colors so that no color touches another color, and then you can have the fourth color for X

@erik3371

4 ай бұрын

How old are you?

I'm always impressed by the quality of these videos. Your cameramen, editors and VFX people must be very talented :)

@adityakhanna113

9 ай бұрын

The VFX is absolutely high-tier!

@atavanH

9 ай бұрын

Music and audio too!

Such a bizarre problem. Normally topological problems like these wind up having a basic explanation when you peel it back; this one has a proof so long we can't read it end to end! Very cool.

The proof of the four colour theorem may be extremely long, but if memory serves, it was still verified (by a team) after the computer produced it. It has also been verified by computers, which is ironically often seen as more rigorous than human verification, since it has to be written in pure logic, making misleading steps impossible.

@ronald3836

9 ай бұрын

Indeed, the whole proof has now been converted into a form that can be checked by a proof checker. The proof checker program is simple enough that its correctness can be verified by a human. Converting a proof into a form that a computer can check is a huge amount of work, but I suppose AI wil lbe able to help us with that in the near future.

@DarkSkay

8 ай бұрын

Is there a correlation between the length of a mathematical statement, problem or question, and the length of corresponding proofs? What kinds of proofs can be shown to be incompressible? When taking statements and corresponding proofs, then applying a set of diverse 'hash functions' on them - will interesting relations between the three leave traces, be preserved or even appear in a different structure?

@caspermadlener4191

8 ай бұрын

@@DarkSkay When looking at the proof of a specific theorem, you generally want to slightly weaken some axioms, and determine whether the theorem still holds. A slightly weaker version of geometry doesn't allow for similar triangles per reflection, and also doesn't have area. Here, the Pythagorean theorem does not necessarily hold. To proof the Pythagorean theorem, you would have to use the similarity of two triangles that are mirrored images of each other, or use area. This only works on relatively simple proofs though. The proof of the four colour theorem is so immensly long that this approach is unrealistic here.

@samwallaceart288

7 ай бұрын

Yeah, if _one_ value is wrong, the computer won't get it

@DarkSkay

7 ай бұрын

@@caspermadlener4191 Thank you! Sometimes, the more I think about what's happening, 'self-constructing', almost organically growing, emerging in maths, the more philosophically mysterious it appears to me. Not only is the number of questions infinite, intuitively the uncountable oceans of 'interesting' ones seem as well - like a natural affinity or family ties between abstract logic structures and the mind. Curiosity never running out of projections and destinations.

Writing this computer proof in IBM 370 assembly language seems like a herculean feat of programming.

The animations at 2:13 are seamless and awesome. Great video :)

@Cahangir

9 ай бұрын

No they are not, one of the joints was wrongly drawn.

@Will.i.am.Mitchell

9 ай бұрын

Is that true?

Give the editor a raise! Good job!

The four colors only hold true for maps without exclaves/enclaves. If you want to color exclaves/enclaves in the same color as the country they belong to then in some cases you might need additional colors.

@Will.i.am.Mitchell

9 ай бұрын

Is that right?

@xavierdarche4822

9 ай бұрын

Try it yourself and you soon figure it out. You could theoretically place hundreds of small enclaves within a country. And if you do that for every country than every country theoretically borders hundreds of countries at the same time and you need hundreds of colors. Of course, this is extreme and doesn’t happen in real life. A real life example. If you would include bodies of water the are territorial and color them as if their land, The Netherlands, Belgium, Germany all border each other and the UK. So, all four need their own colors. Now Belgium, Germany and the UK all border France, (UK borders France across the channel and part Atlantic Ocean) so France would need the same color as The Netherlands. But now, in the Caribbean France borders The Netherlands. So, a fifth color is needed.

@colmkeanly5409

9 ай бұрын

I'm guessing here but I would think including enclaves and exclaves in the map results in non-planar graphs, so the initial assumptions on the question have changed, from a purely 'mathematical' point of view

@ilfedarkfairy

7 ай бұрын

Yeah, I'm kinda suprised that this was not mentioned. This completly changes the maths behind the problem, adding extra dimensions.

@0106johnny

7 ай бұрын

​@@ilfedarkfairyIt makes the maths really easy, because there is a simple way to construct a map with enclaves that can't be colored with n colors or fewer (for any given n). Just take n+1 countries, make them each have an enclave of every other country and boom, you need n+1 colors

The quality of this video is impressive. Thank you.

What about enclaves and exclaves? For example, consider a map with 5 countries, where one of the countries has a small territory inside every other country.

@woland_

8 ай бұрын

The theorem only holds for contiguous regions. Once you add non-contiguous regions like enclaves and exclaves, it starts breaking down.

@danielf.7151

7 ай бұрын

from my understanding, with enclaves and exclaves there is no maximum amount of colors. no matter how many colors you allow, you can always construct a map that needs more than that. for the same reason, countries that only share a corner do not count as adjacent.

@tankadar

7 ай бұрын

yeah exactly ignoring mathematics it is extremely simple to disprove this theory by looking at actual maps. Hell even in the 1800s this was obvious, exclaves were far more common and far more cursed than today, they just needed to think about the german confederation or later the internal borders of the german empire

@zerotwoisreal

7 ай бұрын

easy, let's say you have south africa and lesotho. if south africa is colored red, you can color lesotho any of the other 3 colors, because it only borders one country.

Fascinating story! While I've never had any formal education in graph theory, and unfortunately probably never will, it does appear to be a very approachable and rich subject, ripe for plenty more engaging content such as this video. Might have to pick up a textbook on the subject sometime!

@hrperformance

9 ай бұрын

You definitely should! 😁👍🏼

@richross4781

9 ай бұрын

I guarantee you do not talk like that in real life. Absolutely no chance. Sound like Jordan Peterson, when he babbles on and forgets what he started talking about in the first place. Catch my drift?

@ArawnOfAnnwn

9 ай бұрын

@@richross4781 Wut?

@aug3842

9 ай бұрын

@@richross4781bruh nobody types how they talk irl n this person here did not lose track of their original poiny

Very interesting. Thank you.

Superb video, thanks!!!

great quality of content and visuals!!! love it

quanta always puts out gold. you guys have amazing interesting content

@Will.i.am.Mitchell

9 ай бұрын

❤

Really well explained and excellent animations. Love it!

Fascinating and consequential story. Just one point, in "The Mathematical Tourist", Ivars Peterson (1988) and widely cited in other literature, it is stated that the problem was first proposed in a letter in 1852 written by British graduate student Francis Guthrie to his younger brother, and not from Augustus de Morgan to William Hamilton. Just a point of interest and many thanks - Dave

This is genuinely interesting. I remember reading about the four color theorem in my mathematical logic class and trying to apply Kőnig's lemma to it (with no success).

Assuming that the unavoidable set of 1,936 configurations was rigourously proved, what the computer did was not find any counterexamples to the four-color requirement. It's like disproving Riemann or Fermat by finding one counterexample. The search space is finite, every combination was checked, no counterexamples were found, QED.

6:15 Altgeld Hall at UIUC! I'm doing my math undergrad there. What a beautiful winter picture of the math department building. They're doing renovations right now! :)

Here way before 1m views, but soon you'll get there. Great material, *proof* that is possible to make a great and informative math video in

The explanation and animation are both top notch , Thanks you for the video 😊

Of course the ironic thing is that the *original* theorem is actually a five-colour theorem- because there is always an implicit decision to ignore the *oceans* that surround the area talking about- which on a map will either be blue or white but cannot be considered 'blanks' or 'non-existent' because they're a defined boundary in and of themselves that connects to every point on the outer edge of the graph/map. And if your area has defined oceanic *and* land borders external to the area being coloured that's 6 colours for the final work regardless. And of course Mt. Etna is actually home to a point where 11 municipalities meet (one in fact being enclosed by two arms of another) meaning you just have to shrug and decide that vertices don't count as boundaries. And the whole system just ignores that actual geographical areas might not be contiguous which means that an entity can very easily have borders with *more* 'points' than the graph theoretically suggests. Which is probably why cartographers have never particularly cared about this.

@matejlieskovsky9625

7 ай бұрын

Well, you can assign one of those four colours to the oceans, but lakes will probably not work well. And yes, point borders and exclaves mess the system up, but originally even proving the (now trivial) six colour theorem was a success. Asking if six is the best possible result is only natural.

So nice sir g.

Mantap! Next is ... coloring problem in arbitrary dimension

My old friend Network theory strikes again. Easily the most intriguing aspect of my mathematics degree

How can this video have 731 views when there's only 600 people on earth?

@ashutoshgupta1935

9 ай бұрын

131 from another universe 😂😂

@yoshi314

9 ай бұрын

off by one error

@mal9369

9 ай бұрын

You can watch the video more than once. All of the views actually only come from 13 different people

@shredl0ck

9 ай бұрын

😅

@Cpt_John_Price

9 ай бұрын

Im pretty sure people dont exist, its just a random bunch of numbers that increases with no reason.

Casual reuleaux solid as paperweight at 0:42 with a stack behind him.

Very very very nice.

The skepticism surrounding proofs generated by early computing has a lot of parallels to the current unease surrounding AI generated content today. Doctors and lawyers in particular are having their paradigms shifted by neural networks trained to solve problems that were considered very tough problems only a few short years ago. Just goes to show that the perceptions of the problems we face are constantly shifting!

You know all that footage is from the 50’s and not the 70’s right?

It is a nice video. But it is a mistake at 6:45 to say that every map that contains one of the unavoidable configurations is proven 4-colorable. The actual point is that if a map contains one of the configurations, then it provably is not a minimal counterexample.

This is true. My old laptop can confirm...

Interesting.

Unfortunately this is only true for 2 dimensional maps, is there a known minimum for 3 dimensional maps as those become more common?

is it same as graph bipartitie problem?

Would love to collaborate with Quanta on the history of computers making mathematical conjecture

Does Four-Color Theorem also work for theoretical exclaves? Or does it assume all regions are contiguous?

@mariasolpersico7115

7 ай бұрын

It does not work on enclaves in some cases, because in math the term "map" does not have exclaces

Really well made again. I also like Kempe's (fake) proof, I even once released an April fool's day video proving the four color theorem with it. Despite this, I didn't really understand the idea behind the valid computer-generated proof, and this video just explained it so clearly. Similarly as with Langlads program, it is impressive how you can go deeper than ordinary math youtubers in such a short time and remain easily understandable. By the way coincidentally, I am now working on computer / formal mathematics -- I would like computers to be able to one day solve IMO problems but there is still a long way to go.

Maps tend to be 2D. You don't find a map with an upstairs... or do you? House plans might have any number of "staircases" to the next floor, that has rooms with different coloured carpets. How many different colours of carpet are needed to ensure that the adjacent room doesn't have the same colour? Have I accidentally set another level of challenge?

@thedoczekpl

7 ай бұрын

No, because it can be easily proven that there is no answer (the answer is infinity) [======================== [=^=][=^=][=^=][=^=][=^=][=^=][= There can be one large room upstairs that can be connected to all the rooms downstairs

For some reason, graph coloring seems much more complicated for me

As a digital cartographer, give me any map and I am making it with four colours

I understood the six colour proof.... but five colours already was very hard for me.

I'm really confused on the minimal counterexample argument, because I get it in theory, but here he seemed to take some random variation, show you can do it with 4 colours, and say that proves you can with any map, can someone please explain

@matejlieskovsky9625

7 ай бұрын

The image is not the minimal counterexample. The idea is that IF a minimal counterexample existed, THEN we show that it is not a minimal counterexample (either by solving it or making it smaller) and THEREFORE no minimal counterexample exists. These proofs by contradiction are a bit tricky and really hard to illustrate, since the object you are talking about does not actually exist.

4:42 This is another reason why peer review is so important

"Suppose you want to color the map with four or fewer colors, if you can't there exist smallest map of such"

@ronald3836

9 ай бұрын

All natural numbers are interesting. If this were false, there would be a smallest non-interesting natural number, and that number would be very interesting. QED

Exclaves and enclaves in question:

@skyscraperfan

9 ай бұрын

With enclaves and exclaves the number is not limited, as each country could have an exclave in each other country. Then each country would need a different colour.

My question is, how do they know there are a finite number of unavoidable sets? (1,936 sets)

@tommyrjensen

Ай бұрын

Basically they constructed an unavoidable set of configurations, that is to say, every planar graph provably contains at least one of these. Also the configurations are chosen so that they all are "likely to be" reducible, in the same sense as in Kempe's failed proof. Finally a computer program is used to verify that each configuration is indeed reducible. When they hit on a set of configurations that works, they were done.

Omg that's Dickinson College in Denny Hall!

If you represent the areas of any map with 4 or more areas with a vertices and draw a line between each bordering vertices, (as mentioned in the video), but then translate the vertices into 4 vertices in three dimensions, you will get a three sided pyramid with each vertices being a point and each line connecting a bordering area being an edge for any possible arrangement of four areas. And then if you project this pyramid back onto two dimensions with a light, then one of the connecting lines between the vertices must cross another line, therefore those two vertices (areas) cannot be bordering each other and can be colored using the same color. I am not a mathematician, but is this not a proof?

@Jethro-goro

7 ай бұрын

A three-sided pyramid, aka a tetrahedron, can be flattened without the edges crossing by depicting it as a triangle (the base of the pyramid) with a vertex (the peak) in the center.

What other theorems are proved by computers by now?

why is David S. Richson’s voice SO familiar?!

Historic counties!

Wonder if something like that exists for 3d

Has math solved gerrymandering? Area to circumference ratio

Isn't the simplest proof the fact that you can't draw a clique of five or more without edges intersecting?

@taleladar

8 ай бұрын

Very simple, and elegant.

@SabiaSparrow

7 ай бұрын

No, you need to consider that there's more countries than just the ones bordering the one that you're colouring right now, some other neighbours of the neighbouring countries might have made that colouring invalid already

@killedbyLife

7 ай бұрын

@@SabiaSparrow Give me an example.

@arpitkumar4525

6 ай бұрын

But how do you prove your statement that we can't draw a clique of 5 or more without edges intersecting?

@taleladar

6 ай бұрын

@@arpitkumar4525 Get out a piece of paper, or open some other drawing app. First you put one dot anywhere near the middle. Then you draw another dot nearby and connect with a line. The goal here is to add dots, or vertices, which connect to *all other* dots, but their lines *do not* intersect. These first two steps are trivial, and the only "intersection" you could possibly have is if you put the two dots right on top of each other. Your next task is a third dot, which is also trivially easy. Place the dot anywhere else on the paper that isn't on the line you just drew. Connect all the vertices and now you have a triangle. When you add the fourth dot, this is your first meaningful decision. You only have two options: you can put the dot inside the triangle, or outside it. These are literally your only options, unless you want to put your dot on one of the other lines or dots you drew, which is automatic failure. If you put your dot inside the triangle you had, you can easily connect it to all the other dots and still satisfy the requirements. If you put your dot on the outside, it's possible that you can't. You would have to position the dot so that it is essentially extending from a point on the triangle in order for your new dot to connect to the back two vertices. If you do not position this dot correctly, it can't reach the vertex in the back without crossing an existing line. If you think about what we've done, it is logically impossible to have arrived at any other outcomes. And if you think about it more, both examples we end up with are pretty much the same configuration, but perhaps stretched in certain ways. The last thing to do is try to add a 5th dot which connects to all the vertices, but does not cross any lines. And here is where we run into a problem. Place the dot anywhere inside the bigger triangle, and it is boxed in and can only reach 3 of the 4 previous vertices. Place the dot outside the large triangle, and although you can reach all the outer vertices, you can never reach the inner vertex without crossing a line. This truth is absolutely undeniable, and therefore it is a form of proof. If you are looking for something purely mathematical, I don't think anyone in the comments section has any time to entertain you.

Only issue I have about this theorem is: what if 5 countries touch each other in the same point, like a 5-way star? Or doesn't that single point count as 'bordering'?

@tommyrjensen

Ай бұрын

It doesn't.

How many elegant proofs have we missed doing this?

@tommyrjensen

Ай бұрын

Such as?

@fredroberts8275

Ай бұрын

Well that is kinda the point we don't know.

Yorkshire is massive!

so this only applies to maps with "states" that have five or fewer neighbors?

@SabiaSparrow

7 ай бұрын

No, the proof uses the fact that every map has *at least one* state with five or fewer neighbours, that doesn't mean higher ones don't exist

what about 3d map from starwars

This would make a great project for math students at any age. Ask them, color in this map, so that no neighbors are the same color, and try and use the least amount of colors possible. See who wins.

@skyscraperfan

9 ай бұрын

You raise a good point: While the theorem proves that you can colour any map in four colours, it does not tell you HOW. For a very complicated map you will run into issues, if you you try it by hand. Then you may need some of those complex recolouring algorithms.

@Emc4421

9 ай бұрын

@@skyscraperfan or just like ya know, make the kids think a little and use their brains.

@fernandobanda5734

9 ай бұрын

​@@Emc4421I don't know why you think what the other comment said isn't "using their brain"

Highly recommend Donald Mackenzie's book Mechanizing Proof

I've learned about this from Persona 5

4:00 But this doesn't account for every possible map I wouldn't think

@0106johnny

7 ай бұрын

No, it doesn't work for exclaves. The regions have to be contiguous

How many theorems make a theory? Shapes and Colours make a state?4 points of references=D

1:07 Evidence might be that color was expensive to produce at the time. So, it could be a valid reason, and cartographers are more mathematical than the average joe.

What would a human understandable proof be worth, as in how could the prover's efforts be rewarded? And I don't mean BS such as the accomplishment being reward in itself. I mean financial or livelihood gain.

You can prove this theorem yourself by opening up MSPaint (or any other drawing program) and trying to make 5 different shapes all touch one another. It's trivial to get all three to touch each other, and you can easily make all four shapes touch one another. But when you try to add a 5th, they start blocking each other and getting in the way. Make room for one shape/color to touch another, but then you've cut off another shape/color. This happens no matter what you try to do. I'd say this is also a property of geometry and the limits of 2d space.

@arpitkumar4525

6 ай бұрын

But how do you prove that its impossible to have 5 vertices that connect completely with each other? We can see so its intuitive but maybe we are missing something beyond our intuition and visualization?

@taleladar

6 ай бұрын

@@arpitkumar4525 I guess I don't get what you're asking. If we demonstrate by example that the task is impossible, and exhaust all possibilities, then is that not already proof?

@arpitkumar4525

6 ай бұрын

@@taleladar But how do you know you exhausted all possibilities? There might be something you didn't consider?

great timing to release this story. More AI and learning based methods will be the important in many computational field

Uh oh, a problem?!

Mathematicians failed to consider exclaves and overseas territories.

@Schnoz42069

7 ай бұрын

The word map in math doesn't count enclaves or exclaves

what if a dot has 6 neighbors?

I can solve this Quite easily. Use more colors like maybe 6.

@sourdough4645

9 ай бұрын

Only 4 colors are required, you did not disprove anything.

on second thoughts. some more stuff. Haken died in October last year. his family are also a bunch of geniuses. armin proved some stuff which Pudlak mentions in "proofs as games". the idea of "gameifying" proofs to use human "game play" intuition is interesting. but the actual fact that it works as a strategy is fun. even when it doesnt, which harks back to this problem as a game (see "the map-coloring game" by Bartnicki, Grytczuk, Kierstead and Zhu. as expected, popularised by Gardner) it reveals some great facts about strategy, like Daltonism (colorblindness) might force a player who suggests the game to another to change the game to something similar and yet they can still get a winning stategy that can be back-ported to the original game!!

I wonder how many colors you'd need to color a 3D map?

Wait, wait, wait, wait, does this account for exclaves, and enclaves?

@0106johnny

7 ай бұрын

No. if you add non-contiguous reasons it's easy to create an example that requires more than n colors for any given n

I understood nothing from this video. On one hand, it makes me kinda mad and a bit sad, but also happy that we have so many people understanding it. Please, never support the de-education of peoples.

@skyscraperfan

9 ай бұрын

The idea is that if there were maps that could not be coloured with four colours, we look at a minimal one. Then we delete some countries. As the new map is smaller than the minimal one that requires more than five colours, it can be coloured with four colours. No we add the countries back and prove that the map can still be coloured with four colours. The complicated part is proving that there is a set of subgraphs so that each graph without crossing lines contains at least one of them. If that is proven, you need to find recolouring algorithms for every one of those subgraphs that work with four colours or less.

@Will.i.am.Mitchell

9 ай бұрын

You make a good point!

@Sagittarius-A-Star

8 ай бұрын

👍 for admitting that you don't understand this stuff. If everybody were as honest as you there would be no Covidiots, conspiracy theories, Antivaxxers, .... I guess. Only yesterday I told my daughter that it is not necessarily useless to learn things in school which one will never need again in life - it at least makes one realize that there are things one does not understand but that there ore others who do; so if there is a problem ( like climate change, Covid, ... ), just shut up and let them do their work ( and listen to them ).

Is this related to six degrees of Kevin Bacon? Because it feels like it should be...

take lesotho and separate it in four quarters, all of them will touch each other and will be four colors, now add south africa back and BAM the four color theorem is wrong unless you dont count corners which is fair

@SabiaSparrow

7 ай бұрын

The theorem doesn't count corners If corners are counted, any amount of colours may be necessary because any amount of countries can touch in one point

crazy how this random thought evolved into something that connects the whole world

@_tokorupiel_

3 ай бұрын

...

Can't you have 1 huge country connected to 20 other large countries?

@0106johnny

7 ай бұрын

Yeah, but you can't make the 20 countries border each other

@anonanon2031

7 ай бұрын

@@0106johnny What do you mean you can't? Draw a rectangle, and then draw 20 rectangles 20x smaller than the first, all touching it.

@0106johnny

7 ай бұрын

@@anonanon2031Yeah, but the 20 rectangles wont all touch each other, so you can still use four colors to color them.

@anonanon2031

7 ай бұрын

That is the part I don't understand. Why wouldn't 1 rectangle touch 20 others?@@0106johnny Therefore, requiring you to have 20 colors so no two colors touched...

Is it just me or the paint colour he is wearing looks a bit sus

This theorem would fall apart if two non-neighboring countries decided to build a bridge over a third, causing the map to become three-dimensional.

I’ve created an example where you need 5 colours. When you have to deal with several enclaves. That blows this theory out of the water!

@0106johnny

7 ай бұрын

Obviously this requires contiguous reasons. With exclaves it's really easy to make a map that uses as many colors as you like

The Four Color Theorem, which states that any map can be colored with only four colors without any two adjacent regions sharing the same color, was a longstanding problem in mathematics that was finally solved in 1976 with the use of computers. The problem was initially posed by Francis Guthrie, who wondered if the four-color rule applied to all maps. Mathematicians attempted to solve the problem for decades but couldn't find a proof that satisfied everyone. It wasn't until Kenneth Appel and Wolfgang Haken developed a proof that relied heavily on computers that the problem was finally solved. This sparked a debate about the role of computers in mathematics and what it means to be a mathematician. The proof has wide-ranging applications, from planning wedding seating arrangements to assigning frequencies to radio stations. The problem was originally thought to have come from cartographers, but it was actually posed by mathematicians. The problem can be simplified by converting maps to planar graphs, which are easier to analyze. Mathematicians use graph theory to study relationships between objects, and this helps them analyze the Four Color Theorem. Although the proof is not without controversy, it stands as a testament to the power of computers in mathematics and the innovative thinking of mathematicians.

The simplest shape is a triangle which has three neighbors plus itself = four colors needed = more complex shapes may need less but couid never need more.

GraphQL's origin story?

My proof (if you can call it that) is simpler: the main stress is on the borders. Every country on a map has either an odd or an even number of bordering countries. An even number only requires 2 extra colours to contrast with the home country, while an odd number requires three extra: so no configuration of a country and its neighbours needs more than 4 total colours to distinguish them from one another. This is true of every such instance in 2-D. Each neighbouring country has exactly the same scenario. Exclaves won’t always work though because of an unviable rigidity in such an extension of the system. So it’s a problem of numbers after all. A neat little piece of history with the computer proof being finally clearly a proof after all, which I had previously doubted.

@skyscraperfan

9 ай бұрын

That only proves it for one country and all its neighbours. Both those countries have neighbours themselves. Every graph with no crossing lines can represent a map. So their are endless possibilities.

@TheJohnblyth

9 ай бұрын

and each such country is subject to exactly same constraints and opportunities. I'm not yet convinced I'm wrong, but if you could explain it in simple terms . . .?@@skyscraperfan

@Messilegend1000

9 ай бұрын

​@@skyscraperfanso iin that case, you can have canada swallow usa to create The Great Canadian Empire, with X+Y states....whiiiich still follow the topological rule that that other person mentioned. The 4CT is pro-imperialist, and thus, I reject it, just fyi.

I'd say you can color any map using 3 colors only

@skyscraperfan

9 ай бұрын

No, think about one country surrounded by three other countries, which touch each other. That is the simplest counter example.

@turel528

9 ай бұрын

@@skyscraperfan okay, yeah. I take my statement back. It's 4 colours

When I was a kid I just assumed it was for the same reason that you cannot have more than four shapes each touch each other simultaneously on a 2D plane. Not sure why that would require a complex proof lol.

@xynyde0

8 ай бұрын

" cannot have more than four shapes each touch each other simultaneously on a 2D plane"

@jackdavinci

8 ай бұрын

@@xynyde0 it’s not obvious to me why it wouldn’t be the opposite

@SabiaSparrow

7 ай бұрын

This proves that you can colour a country and its neighbouring countries in just 4 colours, but when you go to the neighbours of the neighbours you might run into a conflict with the colours you've already used, and it's not as simple to prove there's no such conflict

I could break 5 colour therorem in 20 minutes

The "music" is really annoying.

There's an assumption here: Not all countries are geographically continuous.

@Schnoz42069

7 ай бұрын

You misunderstand what the term map means exactly in mathematics

@samsonsoturian6013

7 ай бұрын

@@Schnoz42069 I don't care what the teem map means in math

@Schnoz42069

7 ай бұрын

@@samsonsoturian6013 Hence why you think there is an assumption when there is none

@samsonsoturian6013

7 ай бұрын

@@Schnoz42069 then what does this problem have to do with actual maps?

@mranima748

7 ай бұрын

@@samsonsoturian6013 it has to do with mathematical maps

Insert Simpsons meme: Homer shouting "nerd!".

I'm glad that by increasing use of computers we need less mathematicians.

😮