T1



Theorem:

All regular maps can be simplified by removing all faces with less than five edges, without affecting the search and the validity of the proof. In other words, only maps with all faces with five or more edges can be considered when searching for a demonstration of the problem.

02/Apr/2011 – This theorem was already known. It was found by Kempe back in 1879 in terms of graph theory (see http://en.wikipedia.org/wiki/Four_color_theorem: “Kempe also showed correctly that G can have no vertex of degree 4″). People from http://cstheory.stackexchange.com helped me on this (to find that it was already known). I still think my proof it is of some value, since it is not expressed in terms of graph theory (of the dual graph derived from the map).

Why I think this result is important:

  • Eurer’s identity gets really simplified: 1F5+0F6=12+1F7+2F8+3F9+\char 46\char 46\char 46 and all the weight of the equilibrium is left only on the shoulders of F5 faces
  • Maps that only have faces with 5 edges or more, combined with the use of circular representation of maps, permit to have a different perspective on the problem

Proof:

Following the same pattern used in the book “What Is Mathematics” (Links), it is easy to show that we can consider only maps with faces that have 5 edges or more. Hear is the proof. Consider that up to faces with 3 edges was already proved in the book. This proof removes also faces with 4 edges.

Starting from a given map, we can proceed creating a chain of logical steps, composed of one or more of these statements, until at least one condition is met:

  • If the map has a face with 2 edges
    • remove an edge of this face, and if the new map is 4 colorable, then the old map is also 4 colorable (see “Simplify F2 proof”)
  • If the map has a face with 3 edges
    • remove an edge of this face, and if the new map is 4 colorable, then the old map is also 4 colorable (see “Simplify F3 proof”)
  • If the map has a face with 4 edges
    • remove two opposite edges of this face, and if the new map is 4 colorable, then the old map is also 4 colorable (see “Simplify F4 proof”)

After that the chain of these logical steps has been created, you may end up in one of these two cases: the map has only two faces (easily four colorable) or the map still has many faces (for the Euler’s identity: F5+0F6=12+1F7+2F8+3F9+\char 46\char 46\char 46 these have to be at least 12). For this last case if you find a proof for the simplified map (at the end of the chain), you can walk back (logically) to the original map (the other end of the chain), fully proving the four color theorem (see “Searching for T0“).

Simplify F2 proof

To simplify the map, you can remove an edge of an F2. If you can color the map from which you removed the F2, when you place back the removed face (restoring its edge), it will be always possible to find a color for it, since the restored face will be surrounded by only two colors (two neighbors).

Simplify F3 proof

To simplify the map, you can remove an edge of an F3. If you can color the map from which you removed the F3, when you place back the removed face (restoring its edge), it will be always possible to find a color for it, since the restored face will be surrounded by only three colors (three neighbors).

Simplify F4 proof

To simplify the map, you can remove two edges (not sharing the same vertex) of an F4 (F in the picture). Since the two faces corresponding to the edges you want to remove (B and D in the example) may actually be the same face or adjacent faces (if for example D goes around A or C), in that case take care not to select such edges and select for removing the other two (this is provable as a consequence of the Jordan curve theorem). Let’s continue considering that B and D are different faces not adjacent to each other. If you can color the map from which you removed the edges of the F4, when you restore the removed edges, will be always possible to find a color for the F4, since it will be surrounded by at most three colors (B and D will have the same color).

A colored example of this case is shown here:

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