You see with only four colors you may… Oh wait what?

Earlier today a guy sitting next to me was just killing time by just drawing random figures in MS Paint and using the fill in areas with the fill in tool. I was going to humor him to try to color his picture with as few colors as possible (with the rule that no adjacent zones have the same color). I was presuming that we would end up with something hinting at the 4-color theorem but as I was doodeling I began to realize that there was something weird going on. You see… I only seem to need 2 colors to color my partitions of the plane. The actual partition is created by tracing a continuous line around and only allowing pair-wise intersections and eventually closing it on itself.

PathcoloringI

After some inspection I’ve come to the conclusion that whatever is going on is a consequence of the way I am tracing out the curve, where the fact that I am not allowing  the line to pass though the same point more than twice so every vertex in the corresponding graph always has 4 neighbors which must be the source of it.

Could of course also just be an odd coincidence that my partitions have had this property but I am nevertheless looking forward to figuring out why or how to construct a counterexample.

EDIT: July 2015. Since as it stand I’m probably not making another post on this until I’ve come up with an original proof I’d nevertheless like to add that the result indeed holds and is exclusive dependent on every vertex having even degree (in this case). “The two color theorem” will produce some proofs but if you have Peter Cromwells Polyhedra available at your local library I’d like to recommend it’s chapter on colorings which contains a proof of a slight rephrasing of this result on page 339-341 on top of some other novel results.

Advertisements

One thought on “You see with only four colors you may… Oh wait what?

  1. That’s a neat problem. I suspect you’re right about why these do seem to be 2-colorable but now I’m going to be fiddling with drawing attempted counterexamples.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s