(click on picture for larger view)
Step 1.
Given any map offered as a counter-example, or “criminal”, as exeplified by the Errera map (Fig. 1.0) or the Heawood map (Fig. 2.0), exchange colors in the R-X chain as shown in Fig. 1.1 and 2.1. Note that the new region X shares boundaries with regions colored P,S,Q, and at most one region colored R.
Step 2.
Now exchange colors in the R-Q chain as shown in Fig. 1.2 and Fig 2.2. Note that region X now shares boundaries with regions colored P,S,Q, and at most one region colored R. It’s important to note that regions colored R and S that share a boundary with region X cannot share a boundary with each other. Nor can they be regions in the same R-S chain.
Step 3.
Since regions colored R and S that share a boundary with region X cannot be regions in the same R-S chain, exchanging colors in the R-S chain as shown in Fig. 1.3 and Fig. 2.3 produces a map in which region X is bounded by regions colored with at most three colors, leaving a fourth color available for coloring region X as shown in Fig. 1.4 and 2.4. Thus proper coloring of the entire map with at most four colors is achieved.
Note: Exchanging colors in the S-X chain as
a first step also leads to a proper solution.
a first step also leads to a proper solution.
3 comments:
Your assumption that there can be no R-S chain in Step 2 is incorrect. Hence the proof is incorrect.
Apologies,
Simon
The errera graph, and Heawood graph don't have this chain yes. But other counterexamples that do have it can be constructed. Give it a go yourself :)
Dear dudeysi - thanks so much for stopping by and commenting. I made this blog for my dad, who passed away a year ago at the age of 79. I wanted so much to get him up to speed on the internet so that he could meet like-minded people and have someone knowledgeable to talk to about it. He never did, but he would have loved to have gotten feedback from people like you so he could continue to work on his beloved problem.
This is my dad
best regards, Alicia McCracken Morgan
Post a Comment