Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 43 (2002), No. 2, 583-596.

The Edge-minimal Polyhedral Maps of Euler Characteristic –8 ^{∗}

Ulrich Brehm^{1} Basudeb Datta^{2} Nandini Nilakantan^{2}

1Institut für Geometrie, Technische Universität Dresden D-01062 Dresden, Germany e-mail: brehm@math.tu-dresden.de

2Department of Mathematics, Indian Institute of Science Bangalore 560 012, India e-mail: dattab@math.iisc.ernet.in nandini@math.iisc.ernet.in

Abstract. In [2], a {5, 5}-equivelar polyhedral map of Euler characteristic −8 was constructed. In this article we prove that {5, 5}-equivelar polyhedral map of Euler characteristic −8 is unique. As a consequence, we get that the minimum number of edges in a non-orientable polyhedral map of Euler characteristic −8 is > 40. We have also constructed {5, 5}-equivelar polyhedral map of Euler characteristic −2m for each m ≥ 4. MSC 2000: 52B70, 51M20, 57M20 Keywords: polyhedral maps, polyhedral 2-manifold

1. Introduction

584 U. Brehm et al.: Edge-minimal Polyhedral Maps of Euler Characteristic −8

A finite collection K of cycles, edges and vertices of a complete graph is called a polyhedral complex (of dimension 2) if (i) each edge of a cycle in K is in K, (ii) each vertex of each edge in K is in K and (iii) any two cycles have at most one common edge. The cycles, edges and vertices in a complex are called the faces, edges and vertices in that complex respectively. If u and v are vertices of a face F and uv is not an edge of F then uv is called a diagonal. We denote a face u_{1} ⋯ u_{m}u_{1} by u_{1} ⋯ u_{m} and (u_{1}, …, u_{m}) also. A diagonal (or edge) uv is also denoted by (u, v). A complex is called simplicial if each face is a 3-cycle.

∗This work was initiated when the second-named author was visiting Germany under DAAD programme during May-June, 2000.

0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix} 2002 Heldermann Verlag

For a complex K, the edge graph EG(K) of K is the graph whose vertices and edges are the vertices and edges of K respectively. EG(K) is also called the 1-skeleton of K. See [1] for the graph theoretic terms used in this paper. The vertex-set of K is denoted by V (K).

If K is a complex then we associate another graph Λ(K) with K as follows. The vertices of Λ(K) are the faces in K and for faces F_{1}, F_{2} ∈ K, F_{1}F_{2} is an edge in Λ(K) whenever F_{1} and F_{2} have a common edge. For a vertex u in K let F_{u} be the set of faces containing u. A polyhedral complex K is called a (2-dimensional) abstract polyhedron or an abstract polyhedral 2-manifold if (iv) for each vertex v there is a face F containing v, (v) each edge is in exactly two faces, (vi) the induced subgraph L(u) = Λ(K)[F_{u}] is a cycle for each vertex u in K and (vii) the graph Λ(K) is connected. An abstract polyhedron is called a polyhedral map if (viii) the intersection of any two faces is empty, a vertex or an edge. So, a diagonal in a polyhedral map is the diagonal of a unique face and is not an edge. An abstract simplicial polyhedron is automatically a polyhedral map. Each M_{n} (in Example 5) is a polyhedral map whereas each S_{n} (in Example 6) is an abstract polyhedron but not a polyhedral map.

A polyhedral complex may be thought of as a prescription for the construction of a topological space by pasting together objects which are homeomorphic to the plane polygonal discs. The topological space thus obtained from a complex K is called the geometric carrier of K and is denoted by |K|. It is easy to see that the geometric carrier of an abstract polyhedron is a connected 2-dimensional manifold. An abstract polyhedron K is called orientable (respectively non-orientable) if |K| is orientable (respectively non-orientable).

Two complexes K and L are called isomorphic (denoted by K ≅ L) if there exists a bijective map φ: V (K) → V (L) such that v_{1} ⋯ v_{k} is a face in K if and only if φ(v_{1}) ⋯ φ(v_{k}) is a face in L. We identify two complexes if they are isomorphic. An isomorphism from a complex X to itself is called an automorphism of X. All the automorphisms of X form a group, which is denoted by Aut(X). Clearly, the faces of a complex determine the complex. Because of this we identify a complex with the set of faces in it. If u is a vertex in a complex M then the subcomplex consisting of all the faces through u is called the star of u in M and is denoted by st(u).

If uv is an edge in a complex K then we say u and v are adjacent in K. For a vertex v in a complex K, the number of edges through v is called the degree of v in K. If f_{0}(K), f_{1}(K) and f_{2}(K) are the number of vertices, edges and faces respectively of a complex K then the number χ(K) := f_{0}(K) − f_{1}(K) + f_{2}(K) is called the Euler characteristic of K.

Clearly, if d(K) is the number of diagonals in a polyhedral map K on n vertices then d(K) + f_{1}(K) ≤ \binom{n}{2}. A polyhedral map is called a weakly neighbourly polyhedral map (in short, wnp map) if any pair of vertices are in a face. So, a polyhedral map K is weakly neighbourly if and only if d(K) + f_{1}(K) = \binom{n}{2}.

An abstract polyhedron K is called equivelar of type {p, q} (or {p, q}-equivelar) if each face is a p-gon (i.e., Λ(K) is a p-regular graph) and the degree of each vertex is q (see [3, 4, 5]). We know (see [5]) that there exists a unique equivelar polyhedral map of type {p, q} if (p, q) = (3, 3), (3, 4) or (4, 3) and there are exactly two equivelar polyhedral maps of type {p, q} if (p, q) = (3, 5) or (5, 3). There exist infinitely many (constructed in [5]) {3, q}- equivelar polyhedral maps for q = 6, 7 and 8. For simplicial abstract polyhedra, weakly neighbourly is equivalent to neighbourly. In [5], it is shown that there exist exactly two neighbourly {3, 8}-equivelar polyhedral maps and there exist exactly 14 neighbourly {3, 9}- equivelar polyhedral maps. If M is a neighbourly simplicial map on n vertices then n is 0 or 1 mod 3. Ringel and Jungerman ([6, 7, 8]) have shown that there exist neighbourly non-orientable simplicial maps on n vertices if n = 0 or 1 mod 3 and n ≥ 9 and there exist neighbourly orientable simplicial maps on n vertices if n = 0, 3, 4 or 7 mod 12 and n ≥ 7.

Let K be an abstract polyhedron with faces F_{1}, …, F_{m}. Consider a complex K̃ with vertex-set {w_{1}, …, w_{m}} as: w_{i_{1}} ⋯ w_{i_{k}} is a face in K̃ if and only if there exists a vertex u in K such that F_{i_{1}} … F_{i_{k}}F_{i_{1}} is the cycle L(u) defined above. Then, K̃ is an abstract polyhedron. K̃ is called the dual of K. It is easy to show that the dual of K̃ is isomorphic to K and χ(K̃) = χ(K). Observe that the graph Λ(K) is isomorphic to EG(K̃). Because of this, for an abstract polyhedron K, Λ(K) is called the dual 1-skeleton of K. If K is a {p, q}-equivelar polyhedral map then it is not difficult to see that K̃ is a {q, p}-equivelar polyhedral map. An abstract polyhedron K is called self dual if K is isomorphic to K̃.

If K is a {p, q}-equivelar polyhedral map on n vertices then d(K) = nq(p − 3)/2 and f_{1}(K) = nq/2. So, if K is a {p, q}-equivelar wnp map then nq(p − 3)/2 + nq/2 = n(n − 1)/2 and hence q(p − 2) = n − 1. Here we are interested in the cases when p = q. (In that case n = (p − 1)^{2}.) Clearly, the 4-vertex 2-sphere is the unique {3, 3}-equivelar wnp map. In [2], the first named-author proved that there exist exactly three {4, 4}-equivelar wnp maps (the geometric carriers of two of them are the torus and of one of them is the Klein bottle). Clearly, M_{4} (in Example 5) is a {5, 5}-equivelar wnp map. Here we prove:

Theorem 1. For each m ≥ 2, there exists a self dual orientable {5, 5}-equivelar polyhedral map of Euler characteristic −4m and there exists a self dual non-orientable {5, 5}-equivelar polyhedral map of Euler characteristic −(4m + 2).

Theorem 2. If M is a {5, 5}-equivelar weakly neighbourly polyhedral map then M is isomorphic to M_{4} given below.

From a result (Proposition 8 below) in [2] it follows that if M is a polyhedral map of Euler characteristic −8 then f_{1}(M) ≥ 40. As a consequence of Theorem 2 we get:

Corollary 3. If M is a polyhedral map of Euler characteristic −8 and the number of edges in M is 40 then M is isomorphic to M_{4} given below.

For even number χ ≤ 2, let E_{+}(χ) be the smallest number E for which there exists an orientable polyhedral map of Euler characteristic χ with E edges. Similarly, for χ ≤ 1, let E_{−}(χ) be the smallest number E for which there exists a non-orientable polyhedral map of Euler characteristic χ with E edges. Here we prove:

Corollary 4. E_{−}(−8) > E_{+}(−8) = 40.

Remark 1. For an n-vertex {p, p}-equivelar polyhedral map K the following are equivalent.

(i) K is weakly neighbourly, (ii) n = (p − 1)^{2} and (iii) χ(K) = (p − 1)^{2}(4 − p)/2. So, we can replace the assumption ‘weakly neighbourly’ by ‘16-vertex’ or by ‘of Euler characteristic −8’ in Theorem 2.

Remark 2. We see, from Theorem 2, that there is no non-orientable {5, 5}-equivelar polyhedral map on 16 vertices. Whereas a non-orientable {5, 5}-equivelar abstract polyhedron exists, namely, S_{16}.

Remark 3. For the existence of an n-vertex {5, 5}-equivelar polyhedral map K, n must be even and at least 16. Example 6 shows that there exists an n-vertex {5, 5}-equivelar abstract polyhedron for each even n ≥ 6.

Remark 4. From Ringel and Jungerman’s ([6, 7, 8]) constructions we see that there exist neighbourly orientable and non-orientable simplicial maps on 16 vertices. So, there are more than one {3, 15}-equivelar polyhedral maps on 16 vertices. If we replace each face by a Möbius strip, triangulated with 5 vertices and 5 triangles, then M_{4} leads to a non-orientable neighbourly simplicial map on 16 vertices. In this case each diagonal of M_{4} is converted into an edge. Theorem 2 implies that there is only one such 16-vertex neighbourly map which can be partitioned into sixteen 5-vertex Möbius strips.

2. Examples

Example 5. A sequence of {5, 5}-equivelar polyhedral maps :

M_{n} = {(i, i + 1, i + 2, i + n + 1, i + 2n) : 1 ≤ i ≤ 4n,

additions in the subscripts are modulo 4n}, n ≥ 4.

There are exactly 5 faces through each i, namely, (i, i+1, i+2, i+n+1, i+2n), (i+4n−1, i, i+ 1, i+n, i+2n−1), (i+4n−2, i+4n−1, i, i+n−1, i+2n−2), (i+3n−1, i+3n, i+3n+1, i, i+n−1), (i + 2n, i + 2n + 1, i + 2n + 2, i + 3n + 1, i). Clearly, 5 edges and 10 diagonals through i are distinct. This shows that M_{n} is a polyhedral map and hence a {5, 5}-equivelar polyhedral map. The Euler characteristic of M_{n} is 4n − 10n + 4n = −2n. Polyhedral map M_{4} is weakly neighbourly and was first constructed in [2].

If n is odd then in the geometric realization of M_{n} (given below) the edge (k + n − 1, k) appears twice at the upper row (for odd k) and both in the same direction (i.e., from left to right). Hence |M_{n}| is non-orientable if n is odd. If n is even then there are three types of edges (which have to be pasted to get |M_{n}|), which are of the form (m + n − 1, m), (2k + 1, 2k + 1 + 2n) and (2k, 2k + 2n). Each of first type comes once at the upper row and once at the lower row with the same direction. Each of second (respectively third) type comes twice at the upper (respectively lower) row with different directions (one from left to right and other from right to left). Hence |M_{n}| is orientable if n is even.

Observe that (i, i+1, i+2, i+n+1, i+2n) ↦ 4n−i defines an isomorphism between M̃_{n} and M_{n}. So, M_{n} is self dual. Note that ℤ_{4n} acts vertex-transitively and face-transitively on M_{n}. It is easy to see that Aut(M_{4}) has no element of order 3, 7, 11 or 13. If α is an element of order 5 in Aut(M_{4}) then there exists a vertex v such that α(v) = v and the set of 5 vertices adjacent

[figure: 8; 5; 10; 7; 12; 9; 14; 11; 16; 13; 2; 15; 4; 1; 6; 3; 16; 2; 4; 6; 8; 10; 12; 14; 16; 1; 3; 5; 7; 9; 11; 13; 15; 1; 9; 6; 11; 8; 13; 10; 15; 12; 1; 14; 3; 16; 5; 2; 7; 4; |M_{4}|]

[figure: 10; 6; 12; 8; 14; 10; 16; 12; 18; 14; 20; 16; 2; 18; 4; 20; 6; 2; 8; 4; 20; 2; 4; 6; 8; 10; 12; 14; 16; 18; 20; 1; 3; 5; 7; 9; 11; 13; 15; 17; 19; 1; 11; 7; 13; 9; 15; 11; 17; 13; 19; 15; 1; 17; 3; 19; 5; 1; 7; 3; 9; 5; |M_{5}|]

[figure: ^{· · · · · ·}; ^{· · · · · ·}; 2n; n+1; 2n+2; n+3; 2n+4; n+5; 2n+6; n+7; 2n−8; n−7; 2n−6; n−5; 2n−4; n−3; 2n−2; n−1; 4n; 2; 4; 6; 8; 4n−8; 4n−6; 4n−4; 4n−2; 4n; 1; 3; 5; 7; 9; 4n−7; 4n−5; 4n−3; 4n−1; 1; 2n+1; n+2; 2n+3; n+4; 2n+5; n+6; 2n+7; n+8; 2n−7; n−6; 2n−5; n−4; 2n−3; n−2; 2n−1; n; |M_{n}|]

to v is an α-orbit. Assume, without loss, that v = 16. Then there exists i ∈ {1, 2, 3, 4} such that α^{i}(1) = 8 and hence α^{i} = (1, 8, 13, 3, 15)(2, 9, 12, 6, 7)(5, 10, 11, 14, 4) ∉ Aut(M_{4}), a contradiction. So, σ ∈ Aut(M_{4}) ⇒ order of σ is 2^{n} for some n. If order of σ is 2 then it is easy to show that σ has no fixed point. Thus for any vertex v, Aut(M_{4})_{v} (the isotopy group of v) = {id}. As ℤ_{16} acts vertex-transitively on M_{4} and #(V (M_{4})) = 16, Aut(M_{4}) = ℤ_{16}.

Remark 5. Similar series of {p, p}-equivelar polyhedral maps exist for p ≥ 6 also. These shall be considered in a forthcoming paper.

Example 6. A sequence of {5, 5}-equivelar abstract polyhedra :

S_{2n−1} = {a_{i}a_{i+1}b_{i+n+1}b_{i+n}b_{i+n−1}, a_{i}a_{i+1}b_{i+1}a_{i+n−1}b_{i} : 1 ≤ i ≤ 2n − 1,

additions in the subscripts are modulo 2n − 1},

S_{2n} = {a_{i}a_{i+1}b_{i+n+1}b_{i+n}b_{i+n−1}, a_{i}a_{i+1}b_{i+1}a_{i+n+1}b_{i} : 1 ≤ i ≤ 2n,

additions in the subscripts are modulo 2n}, n ≥ 2.

Since, a_{i}b_{i+n} is an edge as well as a diagonal (for each i) in both S_{2n} and S_{2n−1}, S_{m} is not a polyhedral map for m ≥ 3. Clearly, χ(S_{m}) = −m and hence each S_{2n−1} is non-orientable. By similar arguments as in Example 5, one can show that each S_{2n} is also non-orientable for n ≥ 2. The abstract polyhedra S_{2n} for n ≥ 2 and S_{3} were first constructed in [5].

3. Proofs

In this section we give proofs of our results. We first state two propositions proved by the first-named author in [2]. We need these two propositions to prove Corollaries 3 and 4.

Proposition 7. If M is a polyhedral map then f_{1}(M) ≤ Y (\sqrt{2Y} +2)/8, where Y = f_{0}(M)+ f_{2}(M). Equality holds if and only if M is a {k, k}-equivelar wnp map with f_{0}(M) = f_{2}(M) = (k − 1)^{2} for some k.

Proposition 8. If M is a polyhedral map with Euler characteristic χ then f_{1}(M) ≥ G(χ)−χ, where G(χ) := min\{m ∈ ℕ : m(\sqrt{2m} − 6) ≥ −8χ and m ≥ 8\}.

Proof of Theorem 1. Follows from Example 5. □

Proof of Theorem 2. Let M be a {5, 5}-equivelar wnp map. Then f_{0}(M) = f_{2}(M) = 16. So, M̃ is a {5, 5}-equivelar polyhedral map with f_{2}(M̃) = f_{0}(M̃) = 16 and hence weakly neighbourly. This implies that any two faces of M have a common vertex.

Let the vertices of M be 1, …, 16. We can assume, without loss, that the faces in st(16) are (16, 15, 1, 2, 3), (16, 3, 4, 5, 6), (16, 6, 7, 8, 9), (16, 9, 10, 11, 12) and (16, 12, 13, 14, 15). Clearly, the remaining 11 faces have to be of the form (12, 11, A, B, C), (12, C, D, E, F), (13, 12, F, G, H), (13, H, I, J, K), (13, K, L, M, N), (14, 13, N, O, P), (14, P, Q, R, S), (14, S, T, U, V), (15, 14, V, W, X), (15, X, Y, Z, a) and (1, 15, a, b, c), where A, …, Z, a, b, c ∈ {1, …, 11}.

Claim. (A, B, C) ∈ {(2, 6, 5), (3, 2, 8), (4, 1, 8), (4, 3, 8), (6, 2, 1), (6, 5, 2), (8, 3, 2)}.

Proof of the claim: It is clear that the vertices A, …, H are distinct and none of them can be 9, 10 or 11. So, {A, …, H} = {1, …, 8}. If any three successive vertices (from A, …, Z, a, b, c) are of the form i, i + 1, i + 2, 1 ≤ i ≤ 9, then the degree of one of them will be less than 5. We further see that, if u and v are two vertices in a face not containing 16 then {u, v} ≠ {1, 3}, {3, 5}, {3, 6}, {4, 6}, {6, 8}, {6, 9}, {7, 9} or {9, 11} (since each of these is a diagonal).

If C = 4 then either G or H is 6 and hence one of B or D has to be 3. If D = 3, then {E, F } = {7, 8} and A, B ∈ {1, 2, 5}. This implies that (12, 11, A, B, C)∩(16, 6, 7, 8, 9) = ∅, a contradiction. So, B = 3. Since (12, 11, A, B, C) intersects (16, 6, 7, 8, 9), A = 7 or 8. If A = 7 then D = 8, {E, F } = {1, 2} and {G, H} = {5, 6}. Let (4, 5, a_{1}, a_{2}, a_{3}) and (8, 4, a_{3}, a_{4}, a_{5}) be the last two faces in st(4), where {a_{1}, a_{2}, a_{3}, a_{4}, a_{5}} = {9, 10, 13, 14, 15}. Since both these faces intersect (16, 15, 1, 2, 3), a_{3} = 15. This shows that (13, 15) is a diagonal, a contradiction. So, A ≠ 7. Similarly, A ≠ 8. Thus, C ≠ 4.

[figure: 12; 13; 14; 15; 16; W; X; Y; Z; a; b; c; 1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; A; B; C; V; U; T; S; R; Q; P; O; N; M; L; K; J; I; H; G; F; D; E]

If C = 5 then, with arguments similar to those above, {G, H} = {3, 4} and hence either B or D is 6. If D = 6 then F = 2. This implies that deg(3) < 5, a contradiction. So, B = 6 and hence A = 1 or 2. If A = 1 then {D, E, F } = {2, 7, 8}. If F = 2, then (G, H) = (3, 4), which shows that deg(3) < 5, a contradiction. Thus, F ≠ 2 and hence D = 2. Let the remaining two faces in st(6) be (6, 7, a_{1}, a_{2}, a_{3}) and (1, 6, a_{3}, a_{4}, a_{5}), where a_{1}, a_{2}, a_{3}, a_{4}, a_{5} ∈ {2, 10, 13, 14, 15}. If a_{3} is either 13 or 15, we observe that (13, 15) is either an edge or a diagonal. Since a_{3} ≠ 2, a_{3} has to be 10. We observe that (2, 15) and (13, 15) cannot be edges. Hence (2, 13) and (14, 15) have to be edges in st(6). Since (1, 6, 10, a_{4}, a_{5}) has to have a vertex in common with (13, 12, F, G, H), we see that (a_{4}, a_{5}) = (13, 2) and {a_{1}, a_{2}} = {14, 15}, i.e., {K, L, M, N} = {1, 2, 6, 10} and {V, W, X} = {6, 7, 10}. If H ≠ 3, one face of st(13) will not intersect (16, 15, 1, 2, 3). Hence (G, H) = (4, 3) and K, L, M and N are 10, 6, 1 and 2 respectively. The remaining vertices in st(13) are in {5, 7, 8, 9, 11}. Since (5, 7), (5, 8) and (5, 11) are already diagonals, (5, 9) has to be an edge. Clearly, (O, P) = (5, 9) and {Q, R, S, T, U} = {1, 3, 4, 8, 11}. But, S ∉ {1, 3, 4, 8, 11}. Thus A = 2 and hence (A, B, C) = (2, 6, 5).

Now, assume C ∉ {4, 5}. If A = 1 then B ≠ 3 and C ≠ 2, 3. If B = 2, then C = 6 (since (12, 11, A, B, C) intersects both (16, 6, 7, 8, 9) and (16, 3, 4, 5, 6)). So, (A, B, C) = (1, 2, 6). By a similar argument, we see that

(A, B, C) ∈ {(1, 2, 6), (1, 4, 7), (1, 4, 8), (1, 5, 6), (1, 5, 7), (1, 5, 8), (1, 6, 7), (1, 7, 6), (2, 1, 6),

(2, 3, 7), (2, 3, 8), (2, 4, 7), (2, 4, 8), (2, 5, 6), (2, 5, 7), (2, 5, 8), (2, 6, 7), (2, 7, 6), (3, 2, 7), (3, 2, 8), (3, 4, 7), (3, 4, 8), (3, 7, 8), (3, 8, 7), (4, 1, 7), (4, 1, 8), (4, 2, 7), (4, 2, 8), (4, 3, 7), (4, 3, 8), (4, 7, 1), (4, 7, 2), (4, 8, 1), (4, 8, 2), (5, 1, 7), (5, 1, 8), (5, 2, 7), (5, 2, 8), (5, 6, 1), (5, 6, 2), (5, 7, 1), (5, 7, 2), (5, 8, 1), (5, 8, 2), (6, 1, 2), (6, 2, 1), (6, 5, 1), (6, 5, 2), (6, 7, 1), (6, 7, 2), (7, 2, 3), (7, 3, 2), (7, 4, 1), (7, 4, 2), (7, 4, 3), (7, 5, 1), (7, 5, 2), (7, 6, 1), (7, 6, 2), (7, 8, 3), (8, 2, 3), (8, 3, 2), (8, 4, 1),

(8, 4, 2), (8, 4, 3), (8, 5, 1), (8, 5, 2), (8, 7, 3)}.

If (A, B, C) = (1, 2, 6) then, since (3, 6), (4, 6) and (6, 8) are diagonals, F ∈ {5, 7}. This is impossible, since (5, 6), (6, 7) are edges and C = 6.

Arguing on similar lines, we see that (A, B, C) is not equal to (2, 1, 6), (2, 4, 7), (2, 4, 8), (2, 5, 6),(2, 5, 7), (2, 5, 8), (2, 6, 7), (2, 7, 6), (4, 2, 7), (4, 2, 8), (4, 7, 1), (4, 7, 2), (5, 2, 7),(5, 2, 8), (5, 7, 1), (5, 7, 2), (7, 2, 3), (7, 3, 2), (7, 4, 1), (7, 4, 2), (7, 4, 3), (7, 5, 1), (7, 5, 2), (7, 8, 3) and (8, 7, 3).

If (A, B, C) = (1, 4, 7), then F ∈ {2, 3, 5}. If F ∈ {3, 5}, then (3, 5) will be either an edge or a diagonal in st(12), which is impossible. So, F = 2 and hence either E = 3 or G = 3. If G = 3, then H = 8 and hence (D, E) = (6, 5). This implies, deg(6) < 5. So, E = 3. This implies D = 8 and {G, H} = {5, 6}. Let the remaining two faces in st(7) be (7, 4, a_{1}, a_{2}, a_{3}) and (6, 7, a_{3}, a_{4}, a_{5}), where a_{1}, …, a_{5} ∈ {5, 10, 13, 14, 15}. Since, (5, 6) is an edge, a_{3} ≠ 5. If a_{3} ∈ {13, 15}, then (13, 15) is either an edge or a diagonal in st(7), which is not possible. If a_{3} = 14, then {a_{2}, a_{4}} = {13, 15}, thereby showing that deg(14) < 5. So, a_{3} = 10. In that case, one of these two faces in st(7) does not intersect (16, 15, 1, 2, 3), a contradiction. Arguing on the same lines, we get (A, B, C) ≠ (1, 4, 8).

If (A, B, C) = (1, 5, 6), then {D, E, F } ∩ {3, 4, 7, 8} = ∅. Thus D = E = F = 2, a contradiction. By similar arguments, we see that (A, B, C) ≠ (1, 7, 6), (8, 2, 3) or (8, 4, 3).

If (A, B, C) = (1, 5, 7) then, using the same arguments as those above, F = 2 and hence none of D, E, G or H can be 6, a contradiction. Similarly, (A, B, C) ≠ (5, 1, 7).

If (A, B, C) = (1, 5, 8), then F = 2 and D, E ≠ 6. Therefore, G or H is 6 and hence {G, H} ∩ {3, 4} = ∅. This implies, (D, E) = (4, 3). Then, deg(3) < 5, a contradiction. Similarly, (A, B, C) ≠ (5, 1, 8).

If (A, B, C) = (1, 6, 7), then it is easy to see that F = 2, D ≠ 8 and (3, 8), (4, 5) are edges in st(12). Then (G, H) = (3, 8). In this case, one of the remaining three faces in st(13) will not intersect (16, 15, 1, 2, 3), a contradiction.

If (A, B, C) = (2, 3, 7), then F = 1 and D ∈ {6, 8}. If D is 6, then E ∉ {4, 5, 8}, which is not possible. So, D = 8. Then E = 4 and {G, H} = {5, 6}. Let the last two faces in st(3) be (3, 4, a_{1}, a_{2}, a_{3}) and (7, 3, a_{3}, a_{4}, a_{5}), where {a_{1}, a_{2}, a_{3}, a_{4}, a_{5}} = {8, 9, 10, 13, 14}. Since both these faces intersect (13, 12, 1, G, H), a_{3} = 13. This shows that either a_{2} = 14 or a_{4} = 14. But, in both these cases one of the remaining 2 faces of st(13) will not intersect (16, 15, 1, 2, 3), a contradiction.

If (A, B, C) = (2, 3, 8), then F = 1, D ≠ 6, E ∈ {4, 5}. Therefore, either G or H is 6 and hence one of D or E is 4. If D = 7, then E = 4 and {G, H} = {5, 6}. Let the last two faces in st(8) be (8, 9, a_{1}, a_{2}, a_{3}) and (3, 8, a_{3}, a_{4}, a_{5}). Here, a_{1}, …, a_{5} ∈ {5, 10, 13, 14, 15}. By arguments similar to those above, we observe that it is not possible for a_{3} to be in {5, 10, 13, 14, 15}. So, D ∈ {4, 5} and hence {G, H} = {6, 7}. Let the last two faces in st(8) be (8, 9, c_{1}, c_{2}, c_{3}) and (7, 8, c_{4}, c_{5}, c_{6}). Here, {c_{1}, c_{2}, c_{5}, c_{6}} = {10, 13, 14, 15} and {c_{3}, c_{4}} = {B, D}. Neither c_{1} nor c_{2} can be 10, but one of them should be 13. Thus, {c_{1}, c_{2}} = {13, 14} and {c_{5}, c_{6}} = {10, 15}. Clearly, c_{4} ≠ 3. Thus, (c_{3}, c_{4}) = (3, D). Let the last two faces in st(3) be (3, 8, b_{1}, b_{2}, b_{3}) and (4, 3, b_{3}, b_{4}, b_{5}). Here, b_{1}, …, b_{5} ∈ {7, 9, 10, 13, 14}. Then, by considering st(8), b_{1} = 9 and hence b_{3} ∉ {7, 9, 10, 13, 14}, a contradiction.

If (A, B, C) = (3, 2, 7), then F = 1 and hence, {D, E} = {4, 8} or {5, 6}. Then, by considering st(1), {a, b} = {10, 11}. Now, c = 6. Thus, (D, E, F) = (8, 4, 1) and (G, H) = (6, 5). From st(15), {V, W, X, Y, Z} = {4, 5, 7, 8, 9}. Clearly, X has to be 5 and hence one of (4, 7), (7, 8) or (7, 9) is an edge. But, none of these is possible.

If (A, B, C) = (3, 4, 7), then D ∈ {6, 8}. If D = 6, then {E, F } ∩ {5, 8} = ∅ and thus, {E, F } = {1, 2} and {G, H} = {5, 8}. Let the last two faces in st(7) be (7, 4, a_{1}, a_{2}, a_{3}) and (8, 7, a_{3}, a_{4}, a_{5}). Here, a_{1}, …, a_{5} ∈ {5, 10, 13, 14, 15}. Since both these faces intersect (16, 15, 1, 2, 3), a_{3} = 15. As (13, 15) is already a diagonal, none of the remaining vertices in st(7) can be 13, a contradiction. So, D = 8. Now, F has to be 5 (if E = 5, then {F, G} = {1, 2} and H = 6. This implies that {I, J, K} ∩ {1, 2, 3} = ∅ and hence (13, 6, I, J, K) ∩ (16, 15, 1, 2, 3) = ∅). Then G = 6 and {E, H} = {1, 2}. Let the last two faces in st(5) be (5, E, c_{1}, c_{2}, c_{3}) and (4, 5, c_{3}, c_{4}, c_{5}). Here, c_{1}, …, c_{5} ∈ {9, 10, 11, 14, 15}. Since both these faces intersect (16, 6, 7, 8, 9), c_{3} = 9. Since (9, 11) is a diagonal, none of the remaining vertices in st(5) can be 11, a contradiction.

If (A, B, C) = (3, 4, 8), then F ∉ {6, 7} and G or H = 6. If F = 5 then D = 7, G = 6 and {E, H} = {1, 2}. Let the last two faces in st(5) be (5, E, a_{1}, a_{2}, a_{3}) and (4, 5, a_{3}, a_{4}, a_{5}). Here, a_{1}, …, a_{5} ∈ {9, 10, 11, 14, 15}. Since both these faces intersect (16, 6, 7, 8, 9), a_{3} = 9. This is not possible, since none of the remaining vertices in st(5) can be 11. So, F ≠ 5 and hence, D = 5 (otherwise, (12, 8, D, E, F) ∩ (16, 3, 4, 5, 6) = ∅). Then, {E, F } = {1, 2} and {G, H} = {6, 7}. If (E, F) = (1, 2) then let the last two faces in st(2) be (2, G, b_{1}, b_{2}, b_{3}) and (3, 2, b_{3}, b_{4}, b_{5}), where {b_{1}, b_{2}, b_{3}, b_{4}, b_{5}} = {4, 9, 10, 11, 14}. Clearly, b_{3} = 14. Then, b_{4} and b_{5} cannot be 4 and hence either b_{1} = 4 or b_{2} = 4. This shows that (G, H) = (7, 6). Since (4, 11) is already a diagonal, b_{5} = 11. This shows that b_{4} ≠ 9, which implies that (3, 2, 14, a_{4}, 11) ∩ (16, 6, 7, 8, 9) = ∅. So, (E, F) = (2, 1). From st(1), we see that c ∉ {6, 7}. Hence, a, b, c ∈ {4, 9, 10, 11}. Since one of these vertices has to be 4, none of them can be 11. Thus, {a, b, c} = {4, 9, 10}. The last face in st(1) is (1, H, c_{1}, c_{2}, c). Here {c_{1}, c_{2}} = {11, 14}. This shows that c ∉ {4, 9}. Hence, (a, b, c) = (4, 9, 10). Now, {V, W, X, Y, Z} = {5, 6, 7, 8, 11}. Clearly, X = 7. But, {W, Y } = {6, 8}, thereby showing that deg(7) < 5, a contradiction.

If (A, B, C) = (3, 7, 8), then D = 4, {E, F } = {1, 2} and {G, H} = {5, 6} (if {F, G} = {1, 2}, then H = 6 and hence (13, 6, I, J, K) ∩ (16, 15, 1, 2, 3) = ∅). If (8, 4, a_{1}, a_{2}, a_{3}) and (9, 8, a_{3}, a_{4}, a_{5}) are faces in st(8), then a_{1}, …, a_{5} ∈ {5, 10, 13, 14, 15}. But, a_{3} ∈ {5, 10, 13, 14, 15} is not possible. By a similar argument, (A, B, C) ≠ (3, 8, 7).

If (A, B, C) = (4, 1, 7), then by the same argument as that in the case when (A, B, C) = (1, 4, 7), we see that (D, E, F) = (8, 3, 2) and {G, H} = {5, 6}. Let the last two faces in st(7) be (7, 1, a_{1}, a_{2}, a_{3}) and (6, 7, a_{3}, a_{4}, a_{5}), where a_{1}, …, a_{5} ∈ {5, 10, 13, 14, 15}. It is easy to see that a_{3} = 10, {a_{1}, a_{2}} = {5, 13} and {a_{4}, a_{5}} = {14, 15}. Since (13, 5) is an edge, (G, H) = (6, 5) and thus, from st(7) and st(13), K ∈ {1, 10}. If K = 1, we see that L, M, N ≠ 3. This shows that (13, 1, L, M, N) ∩ (16, 15, 1, 2, 3) = ∅. So, K = 10 and hence (I, J) = (1, 7), N = 3 and {M, O} = {4, 8}. This implies that deg(3) < 5, a contradiction.

If (A, B, C) = (4, 3, 7), then D ∈ {6, 8}. If D = 6, then {E, F } = {1, 2} and {G, H} = {5, 8}. Let the last two faces in st(7) be (7, 8, a_{1}, a_{2}, a_{3}) and (3, 7, a_{3}, a_{4}, a_{5}), where a_{1}, …, a_{5} ∈ {5, 10, 13, 14, 15}. It is easy to see that a_{3} = 10 and {a_{4}, a_{5}} ∩ {5, 15} = ∅. Therefore, (a_{1}, a_{2}) = (5, 15) and {a_{4}, a_{5}} = {13, 14}. Let the last two faces in st(6) be (6, E, b_{1}, b_{2}, b_{3}) and (5, 6, b_{3}, b_{4}, b_{5}), where b_{1}, …, b_{5} ∈ {10, 11, 13, 14, 15}. Comparing st(6) and st(7), we see that b_{5} = 15, (b_{3}, b_{4}) = (11, 14), (b_{1}, b_{2}) = (13, 10) and (a_{4}, a_{5}) = (13, 14). The remaining vertices in st(14) are 1, 2, 4, 7 and 9. This implies, Q, R, S ∈ {2, 7} or {2, 9}, a contradiction. So, D = 8. This implies, {E, F } = {5, 1} or {5, 2}. Let the last two faces in st(7) be (7, 3, c_{1}, c_{2}, c_{3}) and (6, 7, c_{3}, c_{4}, c_{5}), where c_{1}, …, c_{5} ∈ {1, 2, 10, 13, 14, 15}. Clearly, {c_{1}, c_{2}, c_{3}}∩{1, 2, 15} = ∅. Hence, (c_{4}, c_{5}) = (15, 1), {E, F } = {2, 5} and {G, H} = {1, 6}. These imply, c_{3} = 10 and {c_{1}, c_{2}} = {13, 14}. From st(1) and st(2), F ≠ 2 and hence F = 5. This implies, E = 2 and (G, H) = (6, 1). Then deg(6) < 5, a contradiction.

If (A, B, C) = (4, 8, 1), then F = 7 and hence either G = 3 or H = 3. Then {G, H} = {2, 3} and hence (D, E) = (5, 6). This implies that deg(6) < 5, a contradiction. Similarly, (A, B, C) ≠ (8, 4, 1).

If (A, B, C) = (4, 8, 2), then D ∈ {1, 3} and F = 7. If D = 1, then G = 3 or H = 3 and hence {G, H} = {3, 5} or {3, 6}. This is not possible, since (3, 5) and (3, 6) are diagonals. So, D = 3 and hence E ∈ {1, 5, 6}. Again, this is impossible. Similarly, (A, B, C) ≠ (8, 4, 2).

If (A, B, C) = (5, 6, 1), then the last two faces in st(6) are (6, 7, a_{1}, a_{2}, a_{3}) and (1, 6, a_{3}, a_{4}, a_{5}), where a_{1}, …, a_{5} ∈ {2, 10, 13, 14, 15}. It is easy to see that a_{3} = 10. Since, both (2, 15) and (13, 15) cannot be edges, (2, 13) and (14, 15) have to be edges in st(6). Clearly, {a_{4}, a_{5}}∩ {14, 15} = ∅. Therefore, (a_{4}, a_{5}) = (2, 13). These imply, H = 2, G = 3 and I = 1, thereby showing that deg(2) < 5. Similarly, (A, B, C) ≠ (6, 5, 1).

If (A, B, C) = (5, 6, 2), then D ∈ {1, 3}. If D = 1, then {E, F } = {4, 7} or {4, 8}. Let the last two faces in st(2) be (2, 3, a_{1}, a_{2}, a_{3}) and (6, 2, a_{3}, a_{4}, a_{5}), where a_{1}, …, a_{5} ∈ {7, 8, 9, 10, 13, 14}. Clearly, {a_{3}, a_{4}, a_{5}} ∩ {7, 8, 9} = ∅ and either a_{1} or a_{2} is 9. Hence, {a_{1}, a_{2}} = {8, 9}. We see, from st(13), that a_{3} ≠ 13 and (3, 8) is an edge. Clearly, a_{3} ≠ 10. Thus (a_{1}, a_{2}) = (8, 9), (a_{3}, a_{4}, a_{5}) = (14, 13, 10). The remaining vertices in st(14) are 1, 4, 5, 7 and 11. Clearly, {T, U, V } ∩ {7, 11} = ∅. Considering st(12), we see that (E, F) = (4, 7), (G, H) = (8, 3), (T, U, V) = (1, 4, 5) and (W, X) = (11, 7). These imply that deg(5) < 5. So, D = 3 and hence {E, F } = {7, 8}, {G, H} = {3, 4}. By a similar argument as in the case D = 1, we see that D = 3 is also not possible.

If (A, B, C) = (5, 8, 1), then F = 7. It is clear that either G or H = 3 and therefore, (D, E) = (2, 6) and {G, H} = {3, 4}. Let the last two faces in st(6) be (6, 5, a_{1}, a_{2}, a_{3}) and (2, 6, a_{3}, a_{4}, a_{5}), where a_{1}, …, a_{5} ∈ {10, 11, 13, 14, 15}. Since both these faces intersect (13, 12, 7, G, H), a_{3} = 13. This implies that none of a_{1}, a_{2}, a_{4} or a_{5} can be 15, a contradiction. Similarly, (A, B, C) ≠ (5, 8, 2).

If (A, B, C) = (6, 1, 2), then F ∈ {7, 8}, G or H is 3 and hence one of D or E is 5. Now, either {E, F } or {F, G} is {7, 8}. In the first case, D = 5 and {G, H} = {3, 4}. Let the last two faces in st(2) be (2, 3, a_{1}, a_{2}, a_{3}) and (5, 2, a_{3}, a_{4}, a_{5}), where a_{1}, …, a_{5} ∈ {4, 9, 10, 13, 14}. Clearly, a_{5} = 4 and a_{3} = 9. Either a_{1} or a_{4} has to be 13. If a_{1} = 13, we see that a_{2} = 10, a_{4} = 14, (G, H) = (4, 3) and J = 2, thereby showing that deg(3) < 5. If a_{4} = 13, we see that a_{2} = 10, a_{1} = 14 and (G, H) = (3, 4), thereby showing that deg(4) < 5. In the second case, {D, E} = {4, 5} and H = 3. We see that I, J, K ∈ {2, 4, 9, 10, 11}. One of these three vertices has to be 9. Hence neither of the remaining two vertices can be 11 and hence, I = 2 and {J, K} = {9, 10}. Now, N has to be 1. This shows that none of L, M, O or P can be 11, a contradiction.

If (A, B, C) = (6, 7, 1), then let the last two faces in st(6) be (6, 5, a_{1}, a_{2}, a_{3}) and (11, 6, a_{3}, a_{4}, a_{5}), where {a_{1}, a_{2}, a_{3}, a_{4}, a_{5}} = {2, 10, 13, 14, 15}. But, a_{3} ∈ {2, 10, 13, 14, 15} is not possible. Similarly, (A, B, C) ≠ (6, 7, 2).

If (A, B, C) = (7, 6, 1), then repeating earlier arguments, we see that (D, E, F) = (2, 5, 8) and {G, H} = {3, 4}. Let the last two faces in st(6) be (6, 1, b_{1}, b_{2}, b_{3}) and (5, 6, b_{3}, b_{4}, b_{5}), where b_{1}, …, b_{5} ∈ {2, 10, 13, 14, 15}. Clearly, b_{3} ≠ 13 and hence, one of these two faces will not intersect (13, 12, 8, G, H), a contradiction. Similarly, we see that (A, B, C) ≠ (7, 6, 2).

If (A, B, C) = (8, 5, 1), then by arguments similar to those above, we see that (D, E, F) = (2, 6, 7) and {G, H} = {3, 4}. Let the last two faces in st(6) be (6, 5, a_{1}, a_{2}, a_{3}) and (2, 6, a_{3}, a_{4}, a_{5}), where a_{1}, …, a_{5} ∈ {10, 11, 13, 14, 15}. Clearly, a_{3} ≠ 13 and hence one of these two faces does not intersect (13, 12, 7, G, H), a contradiction. Similarly, we see that (A, B, C) ≠ (8, 5, 2). This completes the proof of the claim.

We now show that for each triple (A, B, C), in the claim, M is isomorphic to M_{4}.

Case 1: (A, B, C) = (2, 6, 5). In this case, {D, E, F } ∩ {3, 4} = ∅, and hence D = 1, {E, F } = {7, 8} and {G, H} = {3, 4}. Let the last two faces in st(5) be (5, 1, a_{1}, a_{2}, a_{3}) and (4, 5, a_{3}, a_{4}, a_{5}), where {a_{1}, a_{2}, a_{3}, a_{4}, a_{5}} = {9, 10, 13, 14, 15}. Since both these faces intersect (16, 6, 7, 8, 9), a_{3} = 9. Further, it is clear that either a_{4} or a_{5} is 15. Let the last two faces in st(6) be (6, 2, b_{1}, b_{2}, b_{3}) and (7, 6, b_{3}, b_{4}, b_{5}), where {b_{1}, b_{2}, b_{3}, b_{4}, b_{5}} = {1, 10, 13, 14, 15}. It is clear that b_{3} is 10 and b_{4} or b_{5} is 15 (since (2, 15) is a diagonal). Since (7, 6, 10, b_{4}, b_{5}) must intersect (13, 12, F, G, H), F = 7. Since (1, 7) is a diagonal, (b_{1}, b_{2}) = (1, 13). Comparing st(6) and st(5), we see that (a_{1}, a_{2}) = (13, 14), (a_{4}, a_{5}) = (10, 15) and (b_{4}, b_{5}) = (15, 14). Thus, from st(13), K = 10, (L, M, N) = (6, 2, 1) and (G, H) = (4, 3) (since every face in st(13) must intersect (16, 15, 1, 2, 3)). Now, {I, J, O, P } = {5, 8, 9, 11}. Using the same arguments as those used earlier, (I, J) = (8, 11) and (O, P) = (5, 9). From st(6) and st(5), we see that (V, W, X) = (7, 6, 10) and (Y, Z, a) = (9, 5, 4). Now, it is easy to see that (b, c) = (11, 8), (Q, R, S) = (8, 3, 2) and (T, U) = (11, 4). Here, M is isomorphic, via the map (1, 14, 16, 4, 9, 3, 12, 7, 8, 11, 10, 2, 13, 15)(5, 6), to M_{4}.

Case 2: (A, B, C) = (3, 2, 8). Clearly, F = 1. We see from st(1) that a, b ∈ {9, 10, 11}. Since, (1, 15, a, b, c) intersects (12, 11, 3, 2, 8), one of a, b or c has to be 11. Hence a, b, c ≠ 9 and thus {a, b} = {10, 11}. This implies c = 6 and hence G = 6. Then, from st(15), {V, W, X, Y, Z} = {4, 5, 7, 8, 9}. Clearly, X ∈ {4, 5}, thereby showing that (4, 5) is an edge in st(15). Thus (D, E) = (7, 4) and (G, H) = (6, 5). Since (4, 8) is already a diagonal, X = 5. As (7, 8) and (7, 9) cannot be edges in st(15), (4, 7) and (8, 9) have to be edges in st(15). Now, (Y, Z) = (4, 7) and (a, b) = (11, 10). Comparing st(5) and st(13), (I, J, K) = (8, 2, 10), (V, W) = (9, 8) and N = 3. Here, {M, O} = {4, 11}. Clearly, (L, M) = (9, 4) and (O, P) = (11, 7). Finally, we see that Q, R, S, T and U are 6, 10, 2, 1 and 4 respectively. Now, M is isomorphic, via the map (1, 14, 7, 10, 5, 12)(2, 6, 13, 4, 11)(8, 9), to M_{4}.

Case 3: (A, B, C) = (4, 1, 8). It is easy to see that F = 2 and either G or H is 6. Hence, E = 3. Then, (D, E, F) = (7, 3, 2) and {G, H} = {5, 6}. Let the last two faces in st(8) be (8, 9, a_{1}, a_{2}, a_{3}) and (1, 8, a_{3}, a_{4}, a_{5}). Here, a_{1}, …, a_{5} ∈ {5, 10, 13, 14, 15}. Clearly, a_{3} = 5 and either a_{1} or a_{2} is 15. Since (5, 13) is already a diagonal, (G, H) = (6, 5). As any two faces intersect, (a_{4}, a_{5}) = (13, 10) and {a_{1}, a_{2}} = {14, 15}. Since the last two faces in st(5) intersect (16, 15, 1, 2, 3), a_{2} = 15 and hence a_{1} = 14. Thus (4, 5, 15, 7, 11) is a face. From st(15), we see that (b, c) is (6, 10). Then, {L, M, N, O, P } = {3, 4, 7, 9, 11}. We see that N = 3 and M ≠ 7 (since (7, 10) is already a diagonal). Therefore M = 4, O = 7, L = 9 and P = 11. Finally, we see that Q, R, S, T, U ∈ {1, 2, 4, 6, 10}. Hence, Q = 10, R = 6, S = 2, T = 1 and U = 4. In this case, M is isomorphic, via the map (1, 10, 13, 16, 4, 11, 14, 15, 7, 6, 5, 8, 9, 12), to M_{4}.

Case 4: (A, B, C) = (4, 3, 8). Here D ∈ {1, 2, 5, 7} and E, F ∈ {1, 2, 5}. If D ∈ {1, 2} then, it is easy to see that, E ∈ {1, 2}. In this case, (F, G, H) = (5, 6, 7), thereby showing that deg(6) < 5. Thus, D ∈ {5, 7}. If D = 7 then, since (12, 8, 7, E, F) intersects (16, 3, 4, 5, 6), F = 5. Now, G = 6 (if E = 6, then deg(6) < 5). Let the remaining faces in st(5) be (5, E, a_{1}, a_{2}, a_{3}) and (4, 5, a_{3}, a_{4}, a_{5}). Here, a_{1}, …, a_{5} ∈ {9, 10, 11, 14, 15}. Since both these faces intersect (16, 6, 7, 8, 9), a_{3} = 9. This shows that none of a_{1}, a_{2}, a_{4} or a_{5} is 11, which is not possible. So, D = 5. In this case, {E, F } = {1, 2} and {G, H} = {6, 7}.

The remaining two faces containing 8 are of the form (7, 8, d_{1}, c_{1}, c_{2}) and (8, 9, c_{3}, c_{4}, d_{2}), where {c_{1}, c_{2}, c_{3}, c_{4}} = {10, 13, 14, 15} and {d_{1}, d_{2}} = {3, 5}. If (d_{1}, d_{2}) = (3, 5) then, by using arguments similar to those above, {c_{1}, c_{2}} = {10, 13} and {c_{3}, c_{4}} = {14, 15}. These imply, (I, J, K) = (8, 10, 1) and {V, W, X} = {5, 8, 9}. Then (8, 9, a_{3}, a_{4}, 5) ∩ (13, 12, F, G, H) = ∅. So, (d_{1}, d_{2}) = (5, 3). In this case, {c_{1}, c_{2}} = {10, 15} and {c_{3}, c_{4}} = {13, 14}. These imply, N is either 3 or 9. If N = 3, then {I, J} ∩ ({1, 2} \ {F }) ≠ ∅. These imply, K, L, M ∈ {10, 11}, which is not possible. So, N = 9 and hence (O, P) = (8, 3). These imply, Q = 2 and {R, S} = {7, 10}. Thus, (7, 10) is an edge, thereby showing that (c_{1}, c_{2}) = (15, 10). Since (1, 5) is either an edge or a diagonal in st(12), a ≠ 5. Therefore, a is 10 and (X, Y, Z) = (5, 8, 7). Then {b, c, V, W } = {4, 6, 9, 11}. This implies, {b, c} = {4, 9} or {6, 11}. Since (15, 1, c, b, a) intersects (14, 13, 9, 8, 3), we see that (b, c) = (9, 4). Further, (V, W) = (11, 6), (Q, R, S) = (2, 10, 7) and (T, U) = (1, 4). These imply, (E, F) = (2, 1), (G, H) = (7, 6), (I, J, K) = (11, 10, 2) and (L, M) = (5, 4). Here, M is isomorphic, via the map (1, 8, 13)(2, 9, 14, 4, 11, 3, 12, 16, 15, 7, 5, 10, 6), to M_{4}.

Case 5: (A, B, C) = (6, 2, 1). It is clear that F ∈ {7, 8}, G or H is 3 and hence D or E is 5. Further, either, {E, F } or {F, G} is {7, 8}. If {F, G} = {7, 8}, then {D, E} = {4, 5} and H = 3. It is clear that {J, K} = {9, 10} and I is either 4 or 2. But, this shows that (13, 3, I, J, K) will not intersect either (12, 11, 6, 2, 1) or (12, 1, D, E, F). Thus, {E, F } = {7, 8}. These imply, D = 5 and {G, H} = {3, 4}. Since both the remaining faces in st(1) intersect (16, 6, 7, 8, 9), (a, b, c) = (4, 10, 9). From st(15), we see that {V, W, X, Y, Z} = {5, 6, 7, 8, 11}. Clearly, X = 11 and W = 6. These imply, (Y, Z) = (8, 5), (V, W) = (7, 6) and hence (E, F) = (8, 7). If G = 3 then, by considering st(7), deg(3) < 5. So, G = 4 and hence, H = 3. From st(7), we see that (S, T, U) = (2, 10, 4). Comparing st(13) and st(14), we see that R = 3 and {P, Q} = {8, 9}. Clearly, (I, J, K) = (8, 11, 10) and (P, Q) = (9, 8). These imply, (L, M) = (2, 6) and (N, O) = (5, 1). In this case, M is isomorphic, via the map (1, 2, 5, 10, 6, 13, 7, 12, 15)(3, 8, 11, 14, 4, 9), to M_{4}.

Case 6: (A, B, C) = (6, 5, 2). Let the last two faces in st(6) be (6, 7, a_{1}, a_{2}, a_{3}) and (11, 6, a_{3}, a_{4}, a_{5}), where a_{1}, …, a_{5} ∈ {1, 10, 13, 14, 15}. Clearly, a_{3} = 1. Since (1, 6, 7, a_{1}, a_{2}) ∩ (12, 16, 9, 10, 11) ≠ ∅, a_{1} = 10 or a_{2} = 10. Therefore, {a_{4}, a_{5}} = {13, 14} or {14, 15}. From st(15), we see that {a_{4}, a_{5}} ≠ {14, 15}. Thus, {a_{4}, a_{5}} = {13, 14} and (a_{1}, a_{2}) = (10, 15). These imply, (a, b, c) = (10, 7, 6) and {N, O, P } = {1, 6, 11}. From st(13), we see that N = 1 or P = 1. Hence F, G or H cannot be 1. Thus, D = 1 and E, F ∉ {3, 7}. Hence, {E, F } = {4, 8} and {G, H} = {3, 7}. Let the remaining two faces in st(2) be (2, 3, b_{1}, b_{2}, b_{3}) and (5, 2, b_{3}, b_{4}, b_{5}), where b_{1}, …, b_{5} ∈ {7, 9, 10, 13, 14}. Clearly, b_{3} = 10. Since (3, 7) and (10, 7) are edges, b_{1}, b_{2} ≠ 7 and hence b_{2} = 9, b_{4} = 7 and {b_{1}, b_{5}} = {13, 14}. Now, either (13, 5, 2, 10, 7) or (13, 9, 10, 2, 3) is a face. In both the cases, (14, 13, 1, 6, 11) has to be a face. This implies, (N, O, P) = (1, 6, 11) and (a_{4}, a_{5}) = (13, 14).

If (b_{1}, b_{5}) = (13, 14) then (G, H) = (7, 3), (E, F) = (4, 8), (I, J, K) = (2, 10, 9) and (L, M) = (5, 4). From st(7), we see that (7, 3, 4, 11, 14) is a face, i.e., (Q, R, S) = (4, 3, 7). To complete st(14), (W, X) = (9, 8) and (Y, Z) = (4, 11). In this case, M is isomorphic via the map (1, 12, 16)(2, 13, 15, 4, 11, 8, 3, 14, 7, 6, 9)(5, 10), to M_{4}.

If (b_{1}, b_{5}) = (14, 13) then (G, H) = (3, 7), (E, F) = (8, 4), (I, J, K) = (10, 2, 5) and (L, M) = (9, 8). Then, considering st(14), we get S = 3, T = 2, U = 10 and V = 9. Now, it is clear that (W, X) = (5, 4), (Q, R) = (8, 7) and (Y, Z) = (8, 11). In this case, M is isomorphic via the map (1, 8, 11, 12, 4, 3, 2, 5, 6, 9, 14, 15, 16)(7, 10, 13), to M_{4}.

Case 7: (A, B, C) = (8, 3, 2), then it is clear that F has to be 7 and either G or H has to be 1. So, D, E ∈ {4, 5, 6}. If E = 6, then D = 5, thereby showing that deg(6) < 5. So, E ∈ {4, 5} and hence {D, E} = {4, 5} and (G, H) = (6, 1). Let the last two faces in st(3) be (3, 4, a_{1}, a_{2}, a_{3}) and (8, 3, a_{3}, a_{4}, a_{5}), where {a_{1}, a_{2}, a_{3}, a_{4}, a_{5}} = {7, 9, 10, 13, 14}. Since (8, 3, a_{3}, a_{4}, a_{5}) has to intersect (2, D, E, 7, 12), a_{5} = 7. Thus, a_{3}, a_{4} ∉ {9, 13}. These imply, {a_{1}, a_{2}} = {9, 13} and {a_{3}, a_{4}} = {10, 14}. Let the last two faces in st(2) be (2, D, b_{1}, b_{2}, b_{3}) and (1, 2, b_{3}, b_{4}, b_{5}), where b_{1}, …, b_{5} ∈ {6, 9, 10, 13, 14}. Clearly, b_{1}, b_{2} and b_{3} cannot be 6. Hence, b_{5} = 6, {b_{1}, b_{2}} = {9, 13} and {b_{3}, b_{4}} = {10, 14}. Then, a_{3} is either 10 or 14.

If a_{3} = 10, then (a_{1}, a_{2}) = (13, 9), a_{4} = 14, (b_{3}, b_{4}) = (14, 10) and (b_{1}, b_{2}) = (9, 13). Since (13, 4) is already an edge, (D, E) = (5, 4). Then, by considering st(14), (W, X) = (4, 11). Now, it is clear that (I, J) = (8, 11), (a, b, c) = (5, 9, 8) and (Y, Z) = (10, 6). In this case, M is isomorphic, via the map (1, 3, 10, 9, 8, 11, 12, 15, 4, 13, 16, 7, 14), to M_{4}.

If a_{3} = 14, then (a_{1}, a_{2}) = (9, 13), a_{4} = 10, (b_{3}, b_{4}) = (10, 14) and (b_{1}, b_{2}) = (13, 9). Clearly (D, E) = (5, 4). Then, from st(14), we get W = 5 and X = 11. Now, it is clear that (I, J) = (8, 11), (a, b, c) = (4, 9, 8) and (Y, Z) = (10, 7). Here, M is isomorphic, via the map (1, 3, 14)(2, 6)(4, 13)(7, 10, 9, 12)(8, 11)(15, 16), to M_{4}. This completes the proof. □

Proof of Corollary 3. Let M be a polyhedral map with χ(M) = −8 and f_{1}(M) = 40. Then f_{0}(M) + f_{2}(M) = 40 − 8 = 32. Hence, by Proposition 7, M is a {k, k}-equivelar wnp map with f_{0}(M) = f_{2}(M) = (k − 1)^{2} for some k. Then (k − 1)^{2} = 16 and hence k = 5. Corollary 3 now follows from Theorem 2. □

Proof of Corollary 4. Clearly, G(−8) = 32. So, by Proposition 8, E_{±}(−8) ≥ 40. Since, M_{4} is an orientable wnp map and f_{1}(M_{4}) = 40, Corollary 4 follows from Corollary 3. □

Remark 6. After we proved Theorem 2 theoretically, Ulrich Brehm and Phillip Metzner have got a proof of the same by using computer.

Acknowledgement. We thank the referee for useful comments which led to significant improvements in the presentation of this paper. Remark 4 is also due to the referee.

References

[1] Bondy, J. A., Murty, U. S. R.: Graph Theory with Applications, Macmillan Press, 1976.

[2] Brehm, U.: Polyhedral maps with few edges. Topics in Comb. and Graph Theory (Ringel-Festschrift) (eds. Bodendiek, R. and Henn, R.), Physica-Verlag, Heidelberg 1990, 153– 162. Zbl 0703.57008

[3] Brehm, U., Schulte, E.: Polyhedral maps. Handbooks of Discrete and Computational

Geometry (eds. Goodman, J. E. and O’Rourke, J.), CRC Press 1997, 345–358.

Zbl 0920.52004

[4] Brehm, U., Wills, J. M.: Polyhedral manifolds. Handbook of Convex Geometry (eds. Gruber, P. M. and Wills, J. M.), Elsevier Publishers 1993, 535–554. Zbl 0823.52014

[5] Datta, B., Nilakantan, N.: Equivelar polyhedra with few vertices. Discrete & Comput Geom. 26 (2001), 429–461. Zbl pre01690908

[6] Jungerman, M., Ringel, G.: Minimal triangulations on orientable surfaces. Acta Math. 145 (1980), 121–154. Zbl 0451.57005

[7] Ringel, G.: Wie man die geschlossenen nichtorientierbaren Flächen in möglichst wenig Dreiecke zerlegen kann. Math. Annal. 130 (1955), 317–326. Zbl 0066.41702

[8] Ringel, G.: Map color theorem, Springer, 1974. Zbl 0287.05102

Received June 7, 2001