Proof by Crayon: An Inspired Problem, Part I

I have WordPress Blogger (and Ph.D. mathematics student) Jeremy Kun to thank for inspiring this post. His original post “Graph Coloring, or Proof by Crayon” not only lent me the title, but a ton of fantastic insight into the many, MANY different applications of this kind of mathematics. So, soon-to-be Dr. Kun, many thanks and I hope that you enjoy my take on this.

All right, the first part of this problem is a challenge. Print out (or transfer into paint or some other photo editing software) the map shown below. The challenge is to color the map in as few colors as possible making sure that no two states that touch each other are colored the same color.

Now, do the same thing with the Michigan county map shown below.

Now, do the same thing with the European map shown below.

Now, when you have done that, I want you to put into the comments the number of colors you had to use to meet the requirements of the problems for each map.

Part II will come when we get some data to work with.

Leave a Reply

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

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

Google photo

You are commenting using your Google 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 )

Connecting to %s