The Power of the Four Color Theorem

Today, I will prove last post‘s theorem in a different way assuming the four color theorem. This should illustrate the power of the four color theorem quite nicely. Again, please refer to this post for the definitions of the terms I use.

The four color theorem is as follows: Given a planar graph G, the chromatic number \chi(G)\leq 4.

I assume the four color theorem in order to prove the following theorem about outerplanar graphs.

Theorem: Given an outerplanar graph G, its chromatic number \chi(G)\leq 3.

Proof: If a maximal outerplanar graph on a set of vertices yields a chromatic number less than or equal to 3, then surely, an outerplanar graph on that set of vertices yields a chromatic number less than or equal to 3 as well. Therefore, proving that the chromatic number of a maximal outerplanar graph is less than or equal to three is sufficient to prove our theorem.

maximal outerplanar G

Let a maximal outerplanar graph G be given. Embed another vertex v in the plane somewhere in the unbounded face of G. Connect v to every vertex in G in such a way that no edges cross in G + v; thus, G + v is planar. Clearly, this can be done (see Figure 2).

G + v

Since G + v is planar, by the four color theorem, \chi(G + v) \leq 4. Suppose for a moment that \chi(G + v) = 4 and that the four colors used are {red, blue, green, yellow}. Suppose further, without loss of generality, that v is colored red. Since v is connected to every vertex in G + v, which is properly colored, then v must be the only vertex in G + v colored red. Therefore, G is colored properly with the remaining three colors. So, upon deleting v, we get the properly colored graph G with just three colors. Therefore, \chi(G)\leq 3.

That’s it! As we can see, using the four color theorem allows us to prove a pretty fascinating fact pretty swiftly!

Advertisements

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