Nonexistence of a weakly neighbourly polyhedral map of type \(\{6,6\}\). (English) Zbl 1080.52506

For an \(n\)-vertex polyhedral map of type \(\{p,p\}\) the inequality \(n\geq(p-1)^2\) holds with equality precisely for the class of weakly neighbourly maps, that is, maps with the minimum number of edges. For \(p\leq 5\) it is known that there are such weakly neighbourly maps.
In the present paper it is shown by a computer algorithm that there is none for \(p=6\). Therefore, Brehm’s example of a map of type \(\{6,6\}\) with \(n=26\) is best possible, see U. Brehm in [Topics in combinatorics and graph theory, 153–162 (1990; Zbl 0703.57008)].


52B70 Polyhedral manifolds
51M20 Polyhedra and polytopes; regular figures, division of spaces
57M20 Two-dimensional complexes (manifolds) (MSC2010)
57M15 Relations of low-dimensional topology with graph theory
52-04 Software, source code, etc. for problems pertaining to convex and discrete geometry


edge graph


Zbl 0703.57008
Full Text: DOI EuDML


[1] Brehm U., Topics in Comb, and Graph Theory (Ringel-Fetstschrift) pp 153– (1990)
[2] Brehm U., Beiträge zur Algebra und Geometrie 43 pp 583– (2002)
[3] Brehm U., Handbooks of Discrete and Computational Geometry pp 345– (1997)
[4] Brehm U., Handbook of Convex Geometry pp 535– (1993)
[5] Datta B., Discrete and Comput Geom. 26 pp 429– (2001)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.