A note on nearly Platonic graphs with connectivity one

Dalibor Fronceka , Mahdi Reza Khorsandib, Seyed Reza Musawib, Jiangyi Qiuc

aDepartment of Mathematics and Statistics, University of Minnesota Duluth, Duluth, Minnesota 55812, U.S.A.

bFaculty of Mathematical Sciences, Shahrood University of Technology

P.O. Box 36199-95161, Shahrood, Iran

cDepartment of Mathematics and Statistics, University of Massachusetts Amherst Amherst, MA 01003-9305, U.S.A.

dalibor@d.umn.edu, khorsandi@shahroodut.ac.ir, r musawi@shahroodut.ac.ir, jiangyiqiu@umass.edu

A k-regular planar graph G is nearly Platonic when all faces but one are of the same degree while the remaining face is of a different degree. We show that no such graphs with connectivity one can exist. This complements a recent result by Keith, Froncek, and Kreher on non-existence of 2-connected nearly Platonic graphs.

Keywords: planar graph, regular graph, Platonic graph Mathematics Subject Classification: 05C07, 05C10 DOI: 10.5614/ejgta.2021.9.1.17

1. Introduction

A Platonic graph of type (k, d) is a k-vertex regular and d-face regular planar graph. It is well known that there exist exactly five Platonic graphs, which can be viewed as skeletons of the five Platonic solids—tetrahedron, cube, dodecahedron, octahedron, and icosahedron, of types (3, 3),(3, 4),(3, 5),(4, 3) and (5, 3), respectively.

There are several classes of vertex-regular planar graphs with all but two faces of one degree and two faces of another degree. Hence, it is an intriguing question whether there exist vertex-

Received: 12 June 2020, Revised: 30 December 2020, Accepted: 13 February 2021.

regular planar graphs with exactly one exceptional face? This question was answered in the negative by Deza, Dutour Sikiric, and Shtogrin [2] with a sketch of a proof, and for 2-connected graphs ˇ proved in detail by Keith, Froncek, and Kreher [4].

Theorem 1.1 ([2], [4]). There is no finite, planar, 2-connected, regular graph that has all but one face of one degree and a single face of a different degree.

We complement the result by offering a detailed case-by-case analysis for the remaining case with connectivity one. The main idea of our proof is the following. If such a graph with connectivity one exists, then there must exist an endblock, that is, a 2-connected graph with all vertices but one of degree k, one vertex of degree 1 <l<k, all faces but one of degree d¹ and one face of degree d 6= d1. The non-existence of such graphs was claimed by Deza and Dutour Sikiric in [1]. ˇ Because we were not satisfied with the proof, a purely combinatorial alternative is presented in this paper.

Our goal is to present an alternative proof of the following:

Theorem 1.2 ([1]). There is no finite, planar, regular graph with connectivity one that has all but one face of one degree and a single face of a different degree.

The main idea is to look at the blocks of such a potential graph and show that no endblock with required properties can exist.

The paper is organized as follows. In Section 2, we define the relevant notions and prove some basic observations that will be later used in our further proofs.

In Sections 3, 4, and 5 we discuss in details the non-existence of endblocks of types (3, d),(4, d) and (5, d), respectively.

Finally, in Section 6 we use the lemmas proved in the previous sections to present our proof of Theorem 1.2.

2. Basic notions and observations

We start with a formal definition of an endblock.

Definition 2.1. A (k, d1, d)-endblock B(k,l) is a 2-connected planar graph on n vertices with n1 vertices of degree k, one exceptional vertex x¹ with deg(x1) = l and 1 <l<k, all faces but one of common degree d1, and the remaining face of degree d 6= d1, where the exceptional vertex x¹ belongs to the face of degree d.

We will often use in our arguments the notion of saturated paths.

Definition 2.2. Let G be a 2-connected planar graph with maximum vertex degree k, common face degree d¹ and outerface x1, x2,...,x^d of degree d 6= d1. A vertex u 6= x¹ is k-saturated (or simply saturated) if deg(u) = k and k-unsaturated (or simply unsaturated) if deg(u) < k. Similarly, for a given integer 2 l<k, vertex x¹ is l-saturated (or simply saturated) if deg(x1) = l and l-unsaturated (or simply unsaturated) if deg(x1) < l.

Let a path P = u1, u2,...,u^d1 be an induced subgraph of G such that the graph G + u1u^d1 is still planar and the cycle C = u1, u2,...,u^d1 is a boundary of a face of degree d1. If all vertices

uⁱ for i = 2, 3,...,d¹ 1 are saturated and both u¹ and u^d1 are unsaturated, then P is called a weakly-k-saturated d1-path. If at most one of u¹ or u^d1 is unsaturated while all other vertices are saturated, then P is called a strongly-k-saturated d1-path. When k and d¹ are fixed, we call these paths simply weakly saturated or strongly saturated, respectively.

The following assertions are easy to verify.

Observation 2.3. Let G be a 2-connected planar graph with maximum vertex degree k, minimum face degree d¹ and outerface x1, x2,...,x^d of degree d 6= d1. If a strongly-k-saturated d1-path P = u1, u2,...,u^d1 is on a boundary of an inner face of G, then G cannot be completed into a (k, d1, d)-endblock.

Proof. If G is a subgraph of a (k, d1, d)-endblock, then the whole path P must be a part of an inner face of degree d1, which implies that the remaining edge of that face must be u1u^d1 . However, this edge cannot be added, because at least one of the degrees of u¹ and u^d1 would then exceed k, a contradiction.

Observation 2.4. Let G be a 2-connected planar graph with maximum vertex degree k, minimum face degree d¹ and outerface x1, x2,...,x^d of degree d 6= d1. If a weakly-k-saturated d1-path P = u1, u2,...,u^d1 is on a boundary of an inner face of G, then the edge u1u^d1 must be added in order to complete G into a (k, d1, d)-endblock.

Proof. Similarly as above, the whole path P must be a part of an inner face of degree d1, which implies that the remaining edge of that face must be u1u^d1 . Hence, we must add it to G to complete it into the required endblock.

Observation 2.5. Let G be a subgraph of a (k, 3, d)-endblock B(k,l) and u, v, w be a triangle such that v is saturated and has no neighbors inside the triangle. Then the triangle u, v, w is a face boundary.

Proof. By Observation 2.4, the path u, v, w must be a part of a triangular face. Suppose that u has neighbors inside the triangle. Then at least one of them, say u1, must be on the boundary containing edges u1u and uv. Since v has no neighbors inside the triangle, the boundary also contains the edge vw. But then the edges u1u, uv, vw bound a face that is longer than a triangle, which is impossible.

Now we start eliminating certain forbidden configurations. In a (k, d1, d)-endblock B(k,l) with x1, x2,...,x^d as the boundary of the exceptional face, by a chord we mean an edge xix^j not on the boundary of the exceptional face. That is, if i<j and xix^j is a chord, then j i 6= 1, d 1.

Lemma 2.6. A (3, d1, d)-endblock B(3, 2) for d¹ = 4, 5 does not have a chord.

Proof. Let the cycle x1, x2,...,x^d be the boundary of the exceptional face of this graph and there exists a chord xix^j and j>i. Then j i 3, otherwise j = i + 2 and xixi+1x^j is a triangle such that xⁱ is saturated and has no neighbor inside the triangle. By Observation 2.5, this triangle is the boundary of a face, therefore, xi+1 is of degree 2, which is impossible.

Now, we consider the subgraph H induced by all vertices on and inside the cycle \(x_i, x_{i+1}, \ldots, x_{j-1}, x_j\). Create an isomorphic copy \(\varphi(H) = H'\) of H by assigning \(\varphi(v) = v'\) for every \(v \in H\). Then amalgamate the edges \(x_i x_j\) and \(x_i' x_j'\). The resulting graph is a 2-connected, 3-regular planar graph with all faces of degree \(d_1\) except the outerface, which is of degree 2(j-i). We proved above that \(j-i \geq 3\), which implies that the outerface is of degree \(2(j-i) \geq 6\). Thus we have constructed a 2-connected, 3-regular planar graph with one face of degree greater than 5 and all remaining faces of degree \(d_1 \leq 5\). This contradicts Theorem 1.1.

Lemma 2.7. A (4,3,d)-endblock B(4,l), with the cycle \(x_1, x_2, \ldots, x_d\) as the boundary of the exceptional face does not have a chord, other than \(x_2x_d\) when l=2.

Proof. Let the graph have some chords and the chord \(x_i x_j\) with j > i be the shortest one. It means that there is no other chord \(x_s x_t\) with 0 < t - s < j - i.

If i = 1, then l = 3. In this case the graph has only one vertex of an odd degree, which is impossible.

Now let i>1 and \(y_i\) be the fourth neighbor of \(x_i\). If \(y_i\) is on or inside of the cycle \(x_1,x_2,\ldots,x_i,\) \(x_j,x_{j+1},\ldots,x_d\), then the path \(x_j,x_i,x_{i+1}\) is a weakly-4-saturated 3-path and we must have the triangular face \(x_j,x_i,x_{i+1}\). If j-(i+1)=1, then \(\deg(x_{i+1})=2\), which is impossible and so \(j-(i+1)\geq 2\) and \(x_{i+1}x_j\) is a chord shorter than \(x_ix_j\), a contradiction. Hence, \(y_i\) must be inside of the cycle \(x_i,x_{i+1},\ldots,x_j\). By symmetry, the fourth neighbor \(y_j\) of \(x_j\) must be inside that cycle as well. But then we see that the path \(x_{i-1},x_i,x_j\) is a weakly saturated 3-path and by Observation 2.4, we must have the edge \(x_{i-1}x_j\).

If j < d, then \(x_j\) has neighbors \(x_{i-1}, x_i, y_j, x_{j-1}, x_{j+1}\) and is of degree at least 5, a nonsense. Therefore, j = d and we must have \(x_{i-1} = x_1\), which concludes the proof.

Lemma 2.8. A (5,3,d)-endblock B(5,l), with the cycle \(x_1,x_2,\ldots,x_d\) as the boundary of the exceptional face does not have a chord other than \(x_2x_d\) when l=2.

Proof. Let the graph have some chords and the chord \(x_i x_j\) with j - i > 1 be the shortest one. It means that there is no other chord \(x_s x_t\) with 0 < t - s < j - i.

We denote by C the cycle \(x_i, x_{i+1}, \ldots, x_j\) and by C' the cycle \(x_j, x_{j+1}, \ldots, x_d, x_1, \ldots, x_i\).

First, we consider the case \(i \neq 1\) and so \(\deg(x_i) = \deg(x_j) = 5\). Call \(y_i^1\) and \(y_i^2\) the neighbors of \(x_i\) other than \(x_{i-1}, x_{i+1}, x_j\) and those of \(x_j\) other than \(x_{j-1}, x_{j+1}\) (or \(x_1\)), \(x_i\) similarly \(y_i^1\) and \(y_i^2\).

We will discuss several cases based on placement of the vertices \(y_s^t\) within cycles C and C'.

If both \(y_i^1, y_i^2\) are within C', then the path \(x_j, x_i, x_{i+1}\) is a weakly-5-saturated 3-path and by Observations 2.4 and 2.5, we must have the triangular face \(x_i, x_{i+1}, x_j\). Since j - (i+1) < j - i the edge \(x_{i+1}x_j\) is not a chord. But then \(x_{i+1}\) would have three other neighbors inside that face, which is impossible.

Similarly to the previous case, if both \(y_j^1, y_j^2\) are within C', then the path \(x_i, x_j, x_{j-1}\) is a weakly-5-saturated 3-path and by Observations 2.4 and 2.5, we must have the triangular face \(x_i, x_j x_{j-1}\). Since (j-1)-i < j-i the edge \(x_i x_{j-1}\) is not a chord. But then \(x_{j-1}\) would have three other neighbors inside that face, which is impossible.

If one of \(x_i, x_j\) has both remaining neighbors inside C, say \(x_i\), then the path \(x_{i-1}, x_i, x_j\) is weakly 5-saturated path and we must have edge \(x_{i-1}x_j\) completing the triangle. We observe that

\(x_{i-1}\) cannot have any neighbors inside this triangle. If j=d, then it follows that i-1=1 and l=2 and we are done. If j< d, then by the previous case, \(x_j\) has one neighbor other than \(x_{j-1}\) inside C and the graph bounded by the cycle \(x_{i-1}, x_i, \ldots, x_j, x_{i-1}\) has \(x_{i-1}\) of degree 2 and \(x_j\) of degree 4. Hence, we can take two copies and amalgamate them to obtain a 5-regular graph with the outer face of degree more than 3 and all other faces triangular. However, such a graph does not exist, so this case is impossible.

The only remaining case is that \(x_i\) and \(x_j\) have exactly one neighbor within both C and C'. In this case, we can again obtain a contradiction in a similar manner as in Lemma 2.7. Denote by H the induced subgraph of G consisting of all vertices on or within C and create an isomorphic copy H'. Then amalgamate \(x_i\) with \(x_i'\) and \(x_j\) with \(x_j'\). The resulting graph is a 2-connected 5-regular graph with the outerface of degree 2(j-i)>3 and all other faces of degree 3. Such a graph cannot exist by Theorem 1.1.

Finally, we consider the case i = 1, that is, the graph has a chord \(x_1x_j\) with \(j \neq 2, d\). If l = 3, then \(x_1\) has no neighbor within C and so by Observation 2.4, \(x_2x_j\) is an edge and the graph has a shorter chord than \(x_1x_j\), which is impossible.

For l=4, the vertex \(x_1\) has the fourth neighbor \(y_1^1 \notin \{x_2, x_3, \dots, x_j\} \cup \{x_d\}\).

If \(y_1^1\) is not the inside of C, then as in the previous case, the graph has a shorter chord \(x_2x_j\), a contradiction. Thus, \(y_1^1\) is within C. By applying Observation 2.4 on the weakly-4-saturated 3-path \(x_d, x_1, x_j\), we deduce that the triangle \(x_1, x_d, x_j\) is the boundary of a triangular face of the graph.

We have 1 < j < d. If \(x_j x_d\) is a chord, we find the shortest chord \(x_{i'} x_{j'}\) such that \(j \le i' < j' \le d\) and repeat the case \(i' \ne 1\) from the first part of the proof.

If \(x_j x_d\) is not a chord, by the first part of this proof, and so j = d - 1 and \(deg(x_d) = 2\), which is impossible.

We have exhausted all possibilities and the proof is complete.

Lemma 2.9. Let t be the number of vertices of the \((k, d_1, d)\)-endblock B(k, l) not on the boundary of the outer exceptional face. Then the values of t are as follows:

Proof. Denote the order of the graph by n, the number of its edges by m and the number of faces by f, thus the sum of the vertex degrees will be k(n-1)+l, which is twice the number of edges. By Euler's formula, the number of faces is

\[f = m + 2 - n = \frac{k(n-1) + l}{2} + 2 - n.\]

Also since the sum of the face degrees is twice the number of edges, we have

\[(f-1)d_1 + d = 2m = k(n-1) + l.\]

Solve for n, we have

\[n = \frac{(2-d_1)(k-l) + 2d_1 + 2d}{2k + 2d_1 - kd_1}.\]

Recall that t = n - d, so when we plug in the corresponding values of \(k, d_1\), and l, we obtain our desired values of t as a function of d.

3. Type \((3, d_1)\)

Lemma 3.1. A(3,3,d)-endblock B(3,2) does not exist for any d.

Proof. By Lemma 2.9, we must have d=2 or d=5, otherwise t is not a non-negative integer. Recall that the number of vertices is d+t. If d=2, then t=1 and the graph has 3 vertices in total. Hence, we cannot have vertices of degree 3. When d=5, then t=0 and the graph has 5 vertices in total. By applying Observation 2.4 on the weakly-2-saturated 3-path \(x_5, x_1, x_2\) we conclude that \(x_2x_5\) is an edge of the graph. Now, the path \(x_5, x_2, x_3\) is a strongly-3-saturated 3-path. Hence, the graph has a face with the length greater than 3 and G cannot be completed into B(3,2).

Lemma 3.2. A(3,4,d)-endblock B(3,2) does not exist for any d.

Proof. Recall that by t we denote the number of vertices of B(3,2) inside of the cycle bounding the face of degree d, that is, all vertices other than \(x_1, x_2, \ldots, x_d\). It follows from Lemma 2.9 that t=3.

We denote the internal vertices by \(y_1, y_2\) and \(y_3\). Since \(d_1 = 4\), there are at most two edges \(y_i y_j\), which implies that there are at least five edges \(y_i x_j\). As there is no chord by Lemma 2.6, each \(x_i, i \neq 1\) has exactly one neighbor \(y_j\) and hence \(d \geq 6\). Because \(x_1\) is of degree 2, it is a saturated vertex. Let \(x_2 y_1\) be an edge. Then \(y_1, x_2, x_1, x_d\) is a weakly-3-saturated 4-path, and we must have the edge \(y_1 x_d\).

If the third neighbor of \(x_3\) is \(y_1\), then we have a triangular face, which is impossible. Assume that \(x_3\) is adjacent to \(y_2\). Then \(y_1, x_2, x_3, y_2\) is a weakly-3-saturated 4-path, and we must have the edge \(y_1y_2\). Now, the path \(y_2, y_1, x_d, x_{d-1}\) is a weakly-3-saturated 4-path, and we must have the edge \(y_2x_{d-1}\). Since \(d \ge 6\), we have \(d-1 \ne 4\) and so \(x_4 \ne x_{d-1}\). Then \(x_4, x_3, y_2, x_{d-1}\) is a strongly-3-saturated 4-path, and B(3,2) cannot be completed.

Lemma 3.3. A(3,5,d)-endblock B(3,2) does not exist for any d.

Proof. Assume that the cycle \(x_1, x_2, \ldots, x_d\) is the boundary of the outerface and \(\deg(x_1) = 2\). By Lemma 2.6 the graph has no chord and so each \(x_i\), except \(x_1\), is adjacent to an interior vertex, say \(y_{i-1}\). All \(y_i\)'s are distinct, otherwise as we see in Figure 1(right), if i < j and two vertices \(x_i\) and \(x_j\) have a common interior neighbor, say y, then we have two cycles \(x_i, x_{i+1}, \ldots, x_{j-1}, x_j, y\) and \(x_1, x_2, \ldots, x_i, x_j, x_{j+1}, \ldots, x_d\) and we consider the cycle that the third neighbor of y is not in. If this cycle is a triangle then the graph has an interior triangular face or a cut-vertex, which

Figure 1

is impossible. If this cycle is a square or pentagon then the graph has a cut-vertex, which is impossible. If the length of this cycle is greater than 5 then one of two paths \(x_{i-1}, x_i, y, x_j, x_{j+1}\) or \(x_{i+1}, x_i, y, x_j, x_{j-1}\) is a weakly-3-saturated 5-path and the graph has a chord \(x_{i-1}x_{j+1}\) or \(x_{i+1}x_{j-1}\), respectively, which is impossible.

The path \(y_1, x_2, x_1, x_d, y_{d-1}\) is a weakly-3-saturated 5-path and so \(y_1y_{d-1}\) is an edge.

For any \(1 \le i \le d-1\), the path \(y_i, x_{i+1}, x_{i+2}, y_{i+1}\) is a weakly-3-saturated 4-path and so two vertices \(y_i\) and \(y_{i+1}\) have a common adjacent \(z_i\) to construct a pentagonal face. These vertices are distinct. If \(z_i = z_{i+1}\) for some i, then \(\deg(y_{i+1}) = 2\) and if \(z_i = z_j\), where j - i > 1, then \(\deg(z_i) \ge 4\), which is impossible. If d = 3, then \(z_1\) is a cut-vertex, which is impossible and so d > 4.

If \(d \geq 4\), then the path \(z_{d-2}, y_{d-1}, y_1, z_1\) is a weakly-3-saturated 4-path and two vertices \(z_{d-2}\) and \(z_1\) must have a common neighbor \(w_1\) to obtain a pentagonal face. We have \(w_1 \neq z_i, 2 \leq i \leq d-3\), otherwise \(\deg(w_1) \geq 4\), which is impossible. If d=4, then \(w_1\) is a cut-vertex, which is impossible and so \(d \geq 5\). If \(d \geq 5\), then the path \(w_1, z_1, y_2, z_2\) is a weakly-3-saturated 4-path and two vertices \(w_1\) and \(z_2\) must have a common neighbor \(w_2\) to obtain a pentagonal face (see Figure 1 (left)). We have \(w_2 \neq z_i, 3 \leq i \leq d-4\), otherwise \(\deg(w_2) \geq 4\), which is impossible. If d=5, then \(w_2\) is a cut-vertex and so \(d \geq 6\). If d=6, then the cycle \(w_2 z_2 y_3 z_3\) is the boundary of a square face, which is impossible and so \(d \geq 7\).

If \(d \geq 7\), then the path \(y_{d-3}, z_{d-3}, w_2, z_2, y_3\) is a strongly-3-saturated 5-path and we have an interior face with the length greater than 5, which is impossible.

4. Type (4,3)

For the two remaining cases, we use dual graphs. Recall that the dual graph \(G^D\) of a planar graph G with vertex, edge, and face sets V(G), E(G), F(G), respectively, has \(V(G^D) = F(G)\), \(F(G^D) = V(G)\) and and edge \(e = f_1 f_2 \in V(G^D)\) if and only if the faces \(f_1\) and \(f_2\) share an edge in G. In general, \(G^D\) can be a multigraph with loops. In our case, we only look at dual graphs of

blocks, hence no loops will arise. Concerning multiple edges, we can only have one double edge when l=2.

Lemma 4.1. A (4,3,d)-endblock B(4,l) does not exist for any l and d.

Proof. We cannot have l=3, as in that case the endblock would have a single vertex of an odd degree, a nonsense. Thus, we have l=2.

Figure 2: B(4, 2)

First we show that \(d \ge 4\). Suppose d = 3. Then the outerface is a triangle \(x_1, x_2, x_3\). Vertex \(x_1\) is saturated, hence the inner face containing \(x_1\) is the triangle \(x_1, x_2, x_3\). By Lemma 2.9, we have t = 2, hence there are exactly two other vertices \(y_1\) and \(y_2\), each of degree 4. But then \(y_1\) would have to be adjacent to \(x_2, x_3, y_2\) and also to \(x_1\), which is impossible.

Now we denote the outerface of B(4,2) by f and an inner face containing edge \(x_ix_{i+1}\) by \(f_i\) for \(i=1,2,\ldots,d\). Further, for \(i=2,3,\ldots,d\) the inner face containing \(x_i\) but not sharing an edge with the outerface will be denoted by \(g_i\) (see Figure 2).

Let D be the dual graph of B(4,2). Because \(d \ge 4\), we have \(\deg_D(f) \ge 4\). Notice that we have double edge \(ff_1\) (see Figure 3).

Figure 3: The dual graph of B(4,2)

Let d=3q+r where \(0 \le r \le 2\). We have \(d \ge 4\), hence \(q \ge 1\). We now construct a new graph D' with \(\Delta(D')=3\) as follows. We split vertex f into vertices \(f^0, f^1, \ldots, f^q\) and each \(f^i\) will be incident with edges \(f^i f_{3i+1}, f^i f_{3i+2}, f^i f_{3i+3}\) except possibly for \(f^q\), which may be of degree zero, one, or two (see Figure 4).

The outer boundary is now \(f^0\), \(f_3\), \(g_4\), \(f_4\), \(f^1\), \(f_6\), ..., \(f_1\). If \(f^q\) is of degree zero, then we remove it and obtain an outerface \(f^0\), \(f_3\), \(g_4\), \(f_4\), \(f^1\), \(f_6\), ..., \(f_{d-2}\), \(f_{q-1}\), \(f_1\) of length at least six. But then we

Figure 4: r = 1

have a 2-connected, 3-vertex regular nearly Platonic graph with one face of size at least 6 and all other faces of size 4, which does not exist by Theorem 1.1.

If \(f^q\) is of degree one, as in Figure 4, we remove it and obtain an outerface \(f^0\), \(f_3\), \(g_4\), \(f_4\), \(f_5\), \(f_6\), ..., \(f_{q-1}\), \(f_{d-1}\), \(g_2\), \(f_1\) where \(f_1\) is now of degree two and we have a (3, 4, d')-endblock B(3, 2), which does not exist by Lemma 3.2.

Finally, when \(f^q\) is of degree two, then the boundary is \(f^0, f_3, g_4, f_4, f^1, f_6, \ldots, g_{d-1}, f_{d-1}, f_q, f_1\) where \(f^q\) is now of degree two and then again we have a (3, 4, d')-endblock B(3, 2), which does not exist by Lemma 3.2.

5. Type (5,3)

Lemma 5.1. A (5,3,d)-endblock B(5,l) does not exist for any l and d.

Proof. We again use the dual graph technique to prove the claim. We start with an observation that the case d=3 is impossible. If we have such a graph G with vertex \(x_1\) of degree l where \(1 \le l \le 1\), all other vertices of degree 5, inner faces triangular, and 1 = 1, then the outerface is also a triangle. But then the dual graph \(1 \le 1\) is a 2-connected, cubic graph with one face of degree \(1 \ne 1\), and all remaining faces of degree 5, which is impossible by Theorem 1.1.

If l=2, then the path \(x_3, x_1, x_2\) is weakly saturated, and we must have the edge \(x_2x_3\) completing the boundary of the inner triangular face. But then the remaining neighbors of \(x_2\) and \(x_3\) are outside of the cycle \(x_1, x_2, x_3\), that is, within the outerface, which is impossible.

We use the same notation as in the previous proof, with the exception that for i = 1, 2, ..., d the two inner faces containing \(x_i\) but not sharing an edge with the outerface will be denoted by \(g_i\) and \(h_i\) (see Figure 5).

The case l=2 is essentially the same as for the (4,3,d)-endblock B(4,2) and we omit it.

When l=3, the graphs B(5,3) and its dual graph are shown in Figures 5 and 6, respectively. After splitting vertex f the outerface of D' is \(f^0, f_3, g_4, h_4, f_4, f^1, \ldots, f_1\) of length at least six.

When \(f_q\) is of degree zero, the boundary is \(f^0, f_3, g_4, h_4, f_4, f^1, \ldots, f^{q-1}, f_d, f_1\) and we have a 2-connected, 3-vertex regular nearly Platonic graph with one face of size at least 7 and all other faces of size 5, and such a graph does not exist by Theorem 1.1. When \(f^q\) is of degree one, by omitting \(f^q\), the boundary is \(f^0, f_3, g_4, h_4, f_4, f^1, \ldots, g_d, h_d, f_d, f_1\) and \(\deg(f_d) = 2\), then the outer boundary is of length at least 6, and when \(f^q\) is of degree two, the boundary is \(f^0, f_3, g_4, h_4, f_4, f^1, \ldots, f_{d-1}, f^q, f_d, f_1\) and \(\deg(f^q) = 2\), then the outer boundary is of length

Figure 5: l = 3

Figure 6: The dual graph of B(5,3)

at least 7. In the both cases, we have a (5,3,d')-endblock B(5,3), which does not exist by Lemma 3.2.

When l=4, then the outerface in D' is \(f^0, f_3, g_4, h_4, f_4, f^1, \dots, g_1, f_1\) of length at least seven.

Figure 7: D'

Now similarly as in the previous proof, when \(f_q\) is of degree zero, the boundary is \(f^0\), \(f_3\), \(g_4\), \(h_4\), \(f_4\), \(f^1\), ..., \(f^q\), \(f_d\), \(g_1\), \(f_1\) and we have a 2-connected, 3-vertex regular nearly Platonic graph with one face of size at least 8 and all other faces of size 5, and such a graph does not exist by Theorem 1.1. When \(f^q\) is of degree one, by omitting \(f^q\), the boundary is \(f^0\), \(f_3\), \(g_4\), \(h_4\), \(f_4\), \(f^1\), ..., \(g_d\), \(h_d\), \(f_d\), \(g_1\), \(f_1\) and \(\deg(f_d) = 2\), then the outer boundary is of length at least 7, and when \(f^q\) is of degree two, the boundary is \(f^0\), \(f_3\), \(g_4\), \(h_4\), \(f_4\), \(f^1\), ..., \(f^q\), \(f_d\), \(g_1\), \(f_1\) and \(\deg(f^q) = 2\), then the outer boundary is of length at least 9 (see Figure 7). In the both cases, we have a (5, 4, d')-endblock B(5, 4), which does not exist by Lemma 3.2.

6. Main result

Now we are ready to prove our main result.

Theorem 6.1. There is no \((k, d_1, d)\)-endblock for any admissible triple \((k, d_1, d)\).

Proof. Follows directly from Lemmas 3.1–3.3, 4.1, and 5.1.

An alternative proof of the result presented by Deza and Dutour Sikiric in [1] now follows ˇ immediately.

Theorem 1.2. There is no finite, planar, regular graph with connectivity one that has all but one face of one degree and a single face of a different degree.

Proof. It is well known that every graph with connectivity one and minimum degree at least three has at least two endblocks, that is, 2-connected graphs with minimum degree at least two. If there was a graph defined in the Theorem, it would have to contain a (k, d1, d)-endblock for some admissible triple (k, d1, d). However, such an endblock does not exist by Theorem 6.1. This proves the claim.

References

References

• [1] M. Deza and M. Dutour Sikiric.´ Geometry of Chemical Graphs: Polycycles and Two-Faced Maps. Cambridge University Press, 2008.
• [2] M. Deza and M. Dutour Sikiric, and M. Shtogrin. Fullerene-like spheres with faces of nega- ´ tive curvature. Diamond and related nanostructures 6 (2013) 251–274, edited by Mircea V. Diudea and Csaba L. Nagy.
• [3] D. Froncek and J. Qiu, Balanced 3-nearly Platonic graphs, Bull. Inst. Combin. Appl., 85 (2019), 34–63.
• [4] W. Keith, D. Froncek, and D. Kreher, A note on nearly Platonic graphs, Australas. J. Combin., 70 (2018), 86–103.
• [5] W. Keith, D. Froncek, and D. Kreher, Corrigendum to: A note on nearly Platonic graphs, Australas. J. Combin., 72 (2018), 163.