Is the four color theorem equivalent to the following?
“There can not be a collection of more than four regions on a plane each of which borders each of the others in the collection.”
If it is not equivalent, is there some logical relationship between the theorem and the sentence I just gave above? I.e. if the sentence were true, would this render the 4-color theorem true, or vice versa? Or if the sentence plus something else were true, the 4-color theorem would have to be true, or vice versa? Or anything like that?
That’s equivalent. If there were five regions each bordering all others, four colors would not suffice, and if four colors suffice, there can’t be five regions each bordering all others.
After some searching, I was all set to withdraw my question due to my having read this thread. But now that you’ve given this answer here, I’m confused.
In that other thread, I thought it was established that just because there can’t be five regions each bordering all others on a plane, this doesn’t prove that four colors suffice for all planar graphs. (See your post 48 there and the posts from which it conversationally descends.)
Please clarify so I may quit misunderstanding.
-FrL
In fact, I shared the intuitions Colophon advocated through that thread, and appreciated CJJ’s pointing out that there can be a region on a plane which requires four colors but which does not contain any set of four regions each of which is touching each other. (I had thought any map requiring four colors would have to have four regions in it each of which borders each of the other three. I even though I had a proof of this. Turns out I was wrong…)
I also kind of thought Colophon got unfairly beat up on in that thread. The inductive strategy that seemed so plausible to him also seemed mighty intuitive to me as well. But this is beside the point of the present thread…
That’s right. Don’t confuse a theorem with a “theory”. In science, a theory is a statement that has a body of evidence for it, but in science any theory could conceivably still be proven false if new evidence casts doubt on it. The rules of mathematics are different, though. Absolute proof (within the constraints of the system) is actually possible, and a conjecture only gets theoremhood when such a proof is found.
The answer to your first question is, “No, not in the sense that you can deduce either one as an immediate corollary of the other.”
If you have already proved the four-color theorem, then you can immediately conclude that no five regions can all be touching each other.
However suppose that you had not yet proved the four-color theorem, but you had proved that no five regions can all be touching each other. Then you still wouldn’t have proved the four-color theorem. The problem is that other obstruction might prevent you from completing a four-coloring even though no more than four regions are mutually adjacent.
For example, consider a map that looks like a pizza cut into five slices, where each slice is a country. Then you cannot find three countries such that each borders the other two. Yet you will find that you cannot color this map using only two colors.
Right, that pie-slice diagram is what I was referring to as “CJJ”'s example in my last post. The thread I link to there has satisfied me that what you say is correct.
In that post, I also said I had thought before that I could prove that if a map requires four colors then there are four regions on it that each border each other. But actually, I had (I think) a proof of the weaker statement which I thought equivalent to this, namely the statement that that if a map contains four regions which must be colored four different colors, then somewhere on that map there are four regions which are each touching each of the other three. This I think I might be able to prove. The pie slice thing doesn’t give a counterexample to this because there is noparticular set of four regions on the pie slice which must be given four different colors. Given a four-coloring of that map, it will have four regions each with a different color, but you could recolor the map such that those four regions no longer each have a different color, while the map as a whole retains its four-coloredness and its trait of not having any two bordering regions share a color.
But since the pie slice thing is not a counterexample to this thing I think I might have proved, it follows that this thing I think I might have proved is not of any particular relevance to the four color theorem, so, okay.
Something like that. As I understand it, it breaks the situation down into hundreds of possible cases and uses a computer to check each one, in a way that no unaided human being could do in any reasonable amount of time.
Yep. A statement in math that hasn’t (yet) been proved, but is suspected to be true, is called a conjecture or a hypothesis (as in “The Goldbach Conjecture” or “The Riemann Hypothesis”).
(“Fermat’s Last Theorem” was proved only relatively recently, so technically, it spent most of its life as a conjecture. The reason it was referred to as a theorem is that Fermat claimed to have a proof, though he didn’t write it down and most mathematicians believe that the proof he thought he had was invalid.)
