# Help with distribution and disposition of faces in a map (four color theorem)

For the four coloring problem, maps can be pre-simplified removing all faces that have 2, 3 or 4 edges. In this case the Euler identity becomes: $F_5 + 0F_6 = 12 + F_7 + 2F_8 + 3F_9 + …$. One thing that can be noticed is that pre-simplified maps must have a great number of faces of type $F_5$ (with 5 edges) respect to faces of type $F_7$ or greater. For complex maps (containing faces with a lot of edges) many $F_5$ have to exist. For example for a single face with 1000 edges, 994 faces of type F5 must be added to the Euler identity ($F_5 = … + 994 F_{1000} + …$).

One thing that I initially imagined is that these $F_5$ faces were grouped in cluster, in which an $F_5$ face is surrounded only by other $F_5$ faces. Then I realized that $F_5$ faces could also be mixed with faces of type $F_6$ (which do not alter the Euler identity) or with faces of type >= $F_7$.

I was looking for a paper that analyze the distribution of faces in maps (possibly pre-simplified). Can anybody help?

Just for sharing (not related to this question), one thing that I found analyzing this is that simplified maps of 13 faces do not exist.

-

You can have arbitrary large "partial maps" without any pentagons whatsoever. See the following picture, taken from here:

http://www.mylovedone.com/image/solstice/sum10/HyperbolicCentralPlaceFractals.html

Using this idea you still can get a bona fide "map" with finitely many countries on the sphere. It's just that the pentagons have been moved "far away".

-
The "far far away land" it is full also of F4 faces (squares) :-) Nice category of graphs, thanks! – Mario Stefanutti Jan 31 '13 at 21:33

I think you've misidentified Euler. If $F_n$ is the number of faces with $n$ edges, then you get $$F_5\ge12+F_7+2F_8+3F_9+\cdots$$ From this it is evident, for example, that any (simplified, planar) map must have at least 12 pentagons. Also, if a map has exactly 13 faces, then either they are all pentagons, or there are 12 pentagons and one hexagon. 13 pentagons would imply 13 x 5 / 2 edges which is a nonsense, so that's out. I don't see, offhand, how you rule out 12 pentagons and a hexagon (13 faces, 33 edges, 22 vertices, all of degree 3).

-
I am pretty sure the identity is: $$F_5=12+F_7+2F_8+\cdots$$ Why the ">"? About the simplified map with 13 faces, I verified manually (computer program) that it does not exist. I agree that 13 pentagons is not possible because it would lead to the identity to be 13 = 12. Any other face with more than 6 edges would not work either. If we try with an $F_7$, the equilibrium would bend on the right of the equality and we would need 13 faces of type $F_5$ to balance it. The only possible solutions is to have 12 faces of type $F_5$ + 1 face of type $F_6$ = 13 faces. But these maps do not exist. – Mario Stefanutti Nov 25 '11 at 9:29
$$F = F_2+F_3+F_4+\cdots$$ $$2E = 3V = 2F_2+3F_3+4F_4+\cdots$$ Since a region bounded by n edges has n vertices and each vertex belongs to three regions, by Euler's formula V-E+F = 2 we have: $$6V-6E+6F = 12$$ $$4E-6E+6F = 12$$ $$6F-2E = 12$$ $$6(F_2+F_3+F_4+\cdots)-(2F_2+3F_3+4F_4+\cdots) = 12$$ $$4F_2+3F_3+2F_4+F_5+0F_6-F_7-2F_8-3F_9-\cdots = 12$$ That becomes: $$F_5=12+F_7+2F_8+3F_9+\cdots$$ – Mario Stefanutti Nov 25 '11 at 9:30
Just to make sure I understand: your proof that there are no maps with 12 pentas and 1 hexa is a proof-by-computer? I'm not even sure I see what the search space is. – Gerry Myerson Nov 25 '11 at 10:24
I used a computer program I am building to create simplified maps (sourceforge.net/projects/maps-coloring). The program did not return any map of 13 faces. At the beginning I thought to a bug in the software, then I sketched a proof I thing is right (4coloring.wordpress.com/open-points-and-notes) – Mario Stefanutti Nov 25 '11 at 10:58
I think the 13-region result appears, along with other results that might interest you, in Ruth A Bari's paper, Maximal $m$-gons in 4-regular major maps, Lecture Notes in Mathematics 186 (1971) 5-8. – Gerry Myerson Nov 25 '11 at 11:46