Understanding the Four Color Theorem

[cragar]

I was reading about the four color theorem and I am not sure I understand the statement of the theorem. On wiki it says that you can divide the plane into contiguous regions. I am not sure what they mean by contiguous region. Does that mean that the shapes need to be in contact with one another. Does it matter how many shapes another shape has at its boundaries.

 

[mathman]

Contiguous means each region is connected (only one piece). Also as far as the four color theorem is concerned, there is no vacancy. There are no other limits.

 

[cragar]

Im still not sure what you mean when you say that each region is connected (only one piece ) Like what if I had a circle in the middle and then like 4 regions connected to it, would that work?

 

[Deveno]

Im still not sure what you mean when you say that each region is connected (only one piece ) Like what if I had a circle in the middle and then like 4 regions connected to it, would that work?

only if the circle in the middle is to be colored-in, too. "gaps" aren't fair.

the reason contiguous regions are specified is to avoid the situation that crops up with the continental United States and Alaska, the region "the United States of America" is not contiguous (it has non-touching "pieces").

 

[AlephZero]

Suppose you want to paint a region a particular color. If it is a contiguous region, you could paint the whole region without lifting your paint brush off the surface and putting it down again. It if is a non-contiguous region, you would be forced to pick up the paintbrush and put it down somewhere else.

Another way to explain it is that "contiguous" means you can't "cheat" by saying "I'm going to say these separate regions are all part of one big region, so you have to paint them all the same color". If you could make up "rules" like that, you could invent maps where the minimum number of colors required was arbitrarily large, because you could draw a map where every "region" shared a boundary with every other "region".

 

[cragar]

so basically i could take a sheet of paper . And draw any crazy shapes on it and as many as i want, just as long as there are no gaps on the page.

 

[HallsofIvy]

Also the situation where regions touch in a single point- as a circle divided into many "pies"- is not valid.

 

[phyzguy]

so basically i could take a sheet of paper . And draw any crazy shapes on it and as many as i want, just as long as there are no gaps on the page.

That's right. And I'll bet you can't draw any combination of 'crazy shapes' that take more than four colors.

 

[cragar]

I thought there were more limitations on the map, but it seems like there aren't that many.
Thats a pretty interesting theorem.