2
$\begingroup$

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.

2 Answers 2

3

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

enter image description here

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".

  • 0
    The "far far away land" it is full also of F4 faces (squares) :-) Nice category of graphs, thanks!2013-01-31
0

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).

  • 0
    Sorry, can't help you with that. But pretty much any math library should have the Springer Lecture Notes series, and any library should be able to get it for you on interlibrary loan.2011-12-04