It is already known that in searching for a solution of the four color problem, regular maps can be pre-simplified by removing all faces with less than four edges. This is described for example in the book "What is Mathematics? An Elementary Approach to Ideas and Methods" about the five color theorem.

I belive that all regular maps can be simplified by removing all faces with less than five edges (instead of less then four), without affecting the search and the validity of the four color theorem. This simplification is described here: http://4coloring.wordpress.com/t1/

In this case Euler’s identity gets really simplified: F5 = 12 + F7 + 2F8 + 3 F9 + ...

What is known about this? Has it already been studied before?


The result is known since Kempe in 1879, and is mentioned in http://en.wikipedia.org/wiki/Four_color_theorem as "Kempe also showed correctly that G can have no vertex of degree 4...." Your proof does not work, because when you remove two edges joining face B with A and C, A and C may already have been adjacent. Since you give the combined face a color, then return face B with a new color, you leave A and C adjacent and of the same color.

  • 1
    $\begingroup$ @Jack: If you think the question should be closed it is best not to answer it. $\endgroup$ Apr 2 '11 at 18:22
  • $\begingroup$ @Jack: Thanks for the answer, I completely missed Kempe's proof. I still think my proof is correct and I think it gives a different perspective on the problem, being formulated not in terms of graph theory. I modified the description to make it clearer. I was not able to follow your comment. I never wrote to "replace" anything ("replacing B leaves A and C adjacent"?) and there were not named faces (letters) in my proof ("two edges joining face B with A and C, A and C may ..."?). Anyway it is not important, since the problem has already been answered by Kempe and my question by you. $\endgroup$ Apr 2 '11 at 20:31
  • $\begingroup$ I'm not sure this merits closing for being 'non-research level' because while the answer is "known" it needed an expert to answer it. $\endgroup$ Apr 2 '11 at 21:15
  • 2
    $\begingroup$ Surely doesn't need an expent, Suresh, if the answer is in wikipedia. @Dave, thanks. And Mario, I edited my answer in the hope you'll see that it applies to your proof if the two regions you have adjacent to face 4 are also adjacent to each other. $\endgroup$
    – Jack
    Apr 2 '11 at 21:31
  • 1
    $\begingroup$ @Mario Stefanutti, please read the FAQ. This site is not a discussion forum for "talk[ing] about math and computing", it is a Q&A site for researcher-level questions in TCS. It is also not intended for checking your proofs (it may be acceptable to post them to Math.SE, but first check their FAQ). $\endgroup$
    – Kaveh
    Apr 5 '11 at 0:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.