General Question

mathsphysicsnormally's avatar

Why is it when I draw a closed line shape I can always colour in one section and interchange colours with sections next to eachother so no two sections meet with the same colour?

Asked by mathsphysicsnormally (324points) January 19th, 2011

As shown in my first image
http://img27.imageshack.us/img27/8059/shapesn.jpg
Is a closed line shape, no matter what I do I can’t get it so no matter what you do you would have to have two sections next to each other with the same colour when interchanging colour.

Image two http://img5.imageshack.us/img5/4039/shape1i.jpg
In this image no matter what you do you will have two sections with the same colour next to each other.

Observing members: 0 Composing members: 0

12 Answers

Brian1946's avatar

I think the fact that you need no more than 4 colors so that no two adjacent areas on a plane will have the same color is a topological axiom.

If this is done on a Möbius strip, then a minimum of 7 colors is needed.

mathsphysicsnormally's avatar

@Brian1946
One of my books has a chapter on four colour theorem very interesting but this is more on why is it I only need two for a closed line shape

Brian1946's avatar

The reason you only need two for the first image in your details, is because there are no contiguously adjacent shapes.

the100thmonkey's avatar

There are mathematical theorems behind this?

Seriously, that’s the single most interesting thing I’ve heard since I found out that Basque is a language isolate.

@mathsphysicsnormally: Great question!

@Brian1946: Great answer!

Thanks!

the100thmonkey's avatar

Could either of you two chaps put up a layman’s link for me? It would be smashing to find out more about this.

Brian1946's avatar

@the100thmonkey

I actually learned what little I did from a laydude’s book on topology that I read in the early 1960’s.
I don’t know if that book can be found online, but here’s the wiki on topology.

PhiNotPi's avatar

Any two-dimensional map (an area divided into different regions by boundary lines) is 4-colorable. It can be colored with only four colors, having no similar colored shapes share sides. However, maps like example 1 are a special case- when lines intersect, the intersections always result in four areas meeting at the same point. That is why Four Corners is special, it is the only spot in the US where four states meet at a single point. Given a shape with N number of corners, with every corner being an 4-way intersection, it is impossible for two of its neighbors to touch each other on sides without creating any 3-way intersections. Therefore, if you know that every corner is a 4-way intersection, you know that it is impossible for any of a shape’s neighbors to touch each other, as if they did, it would destroy the fact that there are no 4-way intersections. So, if you color any shape blue, you can safely color all its neighbors blue. You can then safely color all of the neighbor’s neighbor’s red. You can repeat this process until every shape is colored either red or blue, with no two same colored shapes touching. So, they are 2-colorable. Any continous loop or combination of loops, no matter how distorted or with any number of criss-crossings, will only create 4-way intersections. So, any map like example 1 can be colored with two colors.

Example 2, however, contians intersections that are not 4-way, This means that at least one shape has two neighbors that touch each other. In example 2, this is the center shape. This means that the map is not 2-colorable. Some maps which have 3-way intersections are 3-colorable, such as the example, or a grid of hexagons. However, some are only 4-colorable.

Also, any map which is 2-colorable is 3-colorable, and any map that is 3-colorable is also 4-colorable.

mathsphysicsnormally's avatar

I feel so dumb for not getting this now because I even watched a video closely related to it not so long ago
http://www.youtube.com/watch?v=BVVfs4zKrgk

PhiNotPi's avatar

This question actually has nothing to do about three dimensional topography (or any topography, for that matter). It instead is related to with graph coloring, to be more precise planar graph coloring. A graph, in this context, is a group of nodes, each of which are connected to other nodes. A planar graph is a graph that can be laid flat on a 2-d surface, so no connections cross. Planar graphs can be made into maps, were each map is a region, and the connections are were the regions share a side. When a graph is colored, each node is assigned a color so that no two nodes that share a connection share a color. Here is a wikipedia article that talks about graph coloring. However, most of the article is focused on non-planar graph coloring, so you might want to read the article on the four color theorem. This article is focused more on planar graph coloring and map coloring.

mathsphysicsnormally's avatar

@PhiNotPi
¬_¬ Watch the next video and it doesn’t directly answer it but it’s closely related to it

mathsphysicsnormally's avatar

Here’s a somewhat fancy explanation using the index of a curve. Index of a closed curve with respect to some point is the number of revolutions the curve makes around this point. For example, the index of a circle with respect to its center is one (or minus one, depending on the direction), and with respect to an outside point is 0. The index can be any integer number. For example, the index of an 8-shape with respect to points in one of the regions it bounds is +1, with respect to points in another one is -1, and with respect to outside points is 0.
Now you can see that when we cross some part of the curve, the index either increases by one, or decreases by one. If you make a picture, it’s kinda obvious: nothing changes with respect to other parts of the curve, and the one we intersect is ‘passed in another direction’. One can say that we ‘subtract’ or ‘add’ a circle, and the index of a circle is +1 or -1.
So how do we paint the picture? Simple! Paint the regions with even index in white, and the regions with odd index in red.

This is only a small part of the answer but it’s helping me understand

mathsphysicsnormally's avatar

@PhiNotPi
Oh sorry Phi, I’m re going through what you have put

Answer this question

Login

or

Join

to answer.

This question is in the General Section. Responses must be helpful and on-topic.

Your answer will be saved while you login or join.

Have a question? Ask Fluther!

What do you know more about?
or
Knowledge Networking @ Fluther