CONSTRUCTING CERTAIN FAMILIES OF $\mathbf{3}$ -POLYTOPAL GRAPHS

Riccardo W. Maffucci¹¹1EPFL, MA SB Batiment 8, Lausanne, Switzerland. [email protected].

Abstract

Let $n\geq 3$ and $r_{n}$ be a $3$ -polytopal graph such that for every $3\leq i\leq n$ , $r_{n}$ has at least one vertex of degree $i$ . We find the minimal vertex count for $r_{n}$ . We then describe an algorithm to construct the graphs $r_{n}$ . A dual statement may be formulated for faces of $3$ -polytopes. The ideas behind the algorithm generalise readily to solve related problems.

Moreover, given a $3$ -polytope $t_{l}$ comprising a vertex of degree $i$ for all $3\leq i\leq l$ , $l$ fixed, we define an algorithm to output for $n>l$ a $3$ -polytope $t_{n}$ comprising a vertex of degree $i$ , for all $3\leq i\leq n$ , and such that the initial $t_{l}$ is a subgraph of $t_{n}$ . The vertex count of $t_{n}$ is asymptotically optimal, in the sense that it matches the aforementioned minimal vertex count up to order of magnitude, as $n$ gets large. In fact, we only lose a small quantity on the coefficient of the second highest term, and this quantity may be taken as small as we please, with the tradeoff of first constructing an accordingly large auxiliary graph.

Keywords: Algorithm, planar graph, degree sequence, valency, $3$ -polytope, polyhedron.
MSC(2010): 05C85, 52B05, 52B10, 05C07, 05C10, 05C75.

1 Introduction

1.1 The question

Graphs that are planar and $3$ -connected have the nice property of being $1$ -skeletons of $3$ -polytopes, as proven by Rademacher-Steinitz (see e.g. [11, Theorem 11.6]). We call these graphs $3$ -polytopal graphs, or $3$ -polytopes, or polyhedra interchangeably. These special planar graphs are uniquely embeddable in a sphere (as observed by Whitney, see e.g. [11, Theorem 11.5]). Their regions are also called ‘faces’, and are delimited by cycles (polygons) [6, Proposition 4.26].

Our starting point is the following question. Let $n\geq 3$ and $G^{\prime}$ be a $3$ -polytopal graph such that for every $3\leq i\leq n$ , $G^{\prime}$ has at least one $i$ -gonal face. What is the minimal number of faces for $G^{\prime}$ ?

In what follows, we will work on the dual problem. Indeed, it is well-known that $3$ -polytopes have a unique dual graph, that is also $3$ -polytopal (see e.g. [11, Chapter 11]).

Definition 1.

A $3$ -polytope has the property $\mathcal{P}_{n}$ if it has at least one vertex of degree $i$ , for each $3\leq i\leq n$ , and moreover it has minimal order (number of vertices) among $3$ -polytopes satisfying this condition.

The notation $H\prec G$ indicates that $H$ is a subgraph of $G$ . Our first result is the following.

Theorem 2.

Let $n\geq 3$ and $G$ be a $3$ -polytopal graph with at least one vertex of degree $i$ , for every $3\leq i\leq n$ . Then the minimal number $p(n)$ of vertices of $G$ is

p(n)=\left\lceil\frac{n^{2}-11n+62}{4}\right\rceil,\qquad\forall n\geq 14.

(1.1)

For $n\leq 13$ , we have the values in Table 1.

$\begin{array}[]{|c||c|c|c|c|c|c|c|}\hline\cr n&3\leq n\leq 7&8&9&10&11&12&13\\ \hline\cr p(n)&n+1&10&11&14&16&19&23\\ \hline\cr\end{array}$

Table 1: Values of

p(n)

for

n\leq 13

Moreover, starting from $n=14$ and for every $n\geq 16$ , Algorithm 8 constructs a $3$ -polytope $r_{n}$ satisfying $\mathcal{P}_{n}$ and the relations

r_{n}\succ\begin{cases}r_{n-2}&\text{ if }n\equiv 0\pmod{4},\\ r_{n-3}&\text{ if }n\equiv 1\pmod{4},\\ r_{n-4}&\text{ if }n\equiv 2\pmod{4},\\ r_{n-5}&\text{ if }n\equiv 3\pmod{4}\end{cases}\qquad n\geq 16.

(1.2)

Graphs satisfying $\mathcal{P}_{n}$ for $3\leq n\leq 15$ are depicted in Figures 8, 9, 1, and 10.

Theorem 2 will be proven in sections 2, 3, and 4. Passing to the duals, we can answer the original question.

Theorem 2’.

If $n\geq 3$ and $G^{\prime}$ is a $3$ -polytopal graph with at least one $i$ -gonal face, for every $3\leq i\leq n$ , then the minimal number $p(n)$ of faces for $G^{\prime}$ is given by (1.1) and Table 1.

1.2 A related problem

In our next result, given a $3$ -polytope $H$ containing vertices of valencies $\{3,4,\dots,l\}$ , $l\geq 5$ , and an integer $n>l$ , we aim to construct a $3$ -polytope $G$ containing a copy of $H$ as subgraph, and comprising vertices of degrees $\{3,4,\dots,n\}$ . We start with the following definition.

Definition 3.

Let $n\geq 5$ be odd. We say that a $3$ -polytope satisfies property $\mathcal{Q}_{n}$ if there is at least one vertex of degree $3$ , and moreover the polytope contains among its faces the triangles

F_{n;j}=\{v_{n;j;1},v_{n;j;2},v_{n;j;3}\},\quad 1\leq j\leq(n-3)/2

(1.3)

where

\{\deg(v_{n;j;1}):1\leq j\leq(n-3)/2\}\cup\{\deg(v_{n;j;2}):1\leq j\leq(n-3)/2\}=\{4,5,\dots,n\}

(1.4)

and

v_{n;j;3}\neq v_{n;i;1},v_{n;i;2},\quad\forall j,i.

Note that $\mathcal{Q}_{n}$ together with minimality w.r.t. order is stronger than property $\mathcal{P}_{n}$ of Definition 1.

Theorem 4.

Let $l\geq 5$ be odd, and $t_{l}$ be a $3$ -polytope satisfying $\mathcal{Q}_{l}$ . Fix an integer $m\geq 14$ , $m\equiv 2\pmod{4}$ , and let $n:=l+mk$ , where $k$ is a non-negative integer. Then there exists a sequence of $3$ -polytopes

\{t_{n}\}_{n=l+mk,\ k\geq 1},

where each $t_{n}$ satisfies $\mathcal{Q}_{n}$ , such that along the sequence, for all $\epsilon>0$ , one has

|V(t_{n})|\leq\frac{n^{2}}{4}-\frac{11n}{4}+\left(\frac{5}{2m}+\epsilon\right)n

(1.5)

as $n\to\infty$ . Moreover, for all $k\geq 1$ , it holds that

t_{l+m(k-1)}\prec t_{l+mk}.

(1.6)

For chosen $t_{l}$ and $N\geq 1$ , Algorithm 13 constructs $t_{l+mk}$ for $1\leq k\leq N$ .

Theorem 4 will be proven in section 6.

Remark 5.

The order (1.5) of the sequence of polyhedra in Theorem 4 is asymptotically optimal, in the sense that the leading term is $n^{2}/4$ as in (1.1). The coefficient of the linear term is only slightly larger than the $-11n/4$ of (1.1). This difference can be taken as small as we please if $m$ is chosen to be large, with the tradeoff of first constructing an accordingly large auxiliary graph $s_{m+3}$ , as detailed in sections 5 and 6.

Remark 6.

In Definition 3, we could have supposed instead $n$ even. Then accordingly one would have taken $j\leq(n-2)/2$ in (1.3), and the set $\{3,4,\dots,n\}$ on the RHS of (1.4). This would have produced similar setup and ideas.

1.3 Related literature, notation, and plan of the paper

Related literature.

Necessary conditions for the degree sequence of a planar graph were given in [3, 5]. On the other hand, Eberhard [7] proved that any degree sequence where $q=3p-6$ ( $p,q$ being vertex and edge counts respectively) may be made planar by inserting a sufficiently large number of $6$ ’s. There have been numerous generalisations and extensions since, see e.g. [1, 2, 9, 10, 13, 14]. In [12], the authors determine the sequences for regular, planar graphs. This was extended in [15] to sequences with highest and lowest valencies differing by one or two.

Notation.

All graphs that appear contain no loops and multiple edges. The vertex and edge sets of a graph $G$ are denoted by $V(G)$ and $E(G)$ respectively. The order and size of $G$ are the numbers $|V(G)|$ and $|E(G)|$ . The degree or valency $\deg_{G}(v)$ of a vertex $v$ counts the number of vertices adjacent to $v$ in $G$ . We use the shorthand $\deg(v)$ when $G$ is clear. The degree sequence of $G$ is the set of all vertex valencies.
We write $G\cong H$ when $G,H$ are isomorphic graphs, and $H\prec G$ when $H$ is (isomorphic to) a subgraph of $G$ .
A graph of order $k+1$ or more is said to be $k$ -connected if removing any set of $k-1$ or fewer vertices produces a connected graph.
Regions of a $2$ -connected planar graph are cycles of length $i$ ( $i$ -gons) [6, Proposition 4.26]. For these graphs, the terms ‘region’ and ‘face’ are interchangeable. The $i$ -gonal faces will be denoted by their sets of $i$ vertices. If $\{a,b,c\}$ is a triangle, we call splitting the operation of adding a vertex $d$ and edges $da,db,dc$ .

Plan of the paper.

Theorem 2 is proven in sections 2 (lower bound (1.1)), 3 (cases $n\leq 13$ ) and 4 (Algorithm 8 for $n\geq 14$ ). Section 5 is about an application of a similar flavour, that we can tackle via a minor modification of Algorithm 8. The theory of section 5 will also be useful in section 6 to prove Theorem 4.
Appendix A presents another way to think about Algorithm 8. Appendix B contains figures of graphs mentioned in sections 3 and 4.

1.4 Acknowledgements

The author was supported by Swiss National Science Foundation project 200021_184927.

2 The lower bound

In this section we prove (1.1).

Lemma 7.

Let $n\geq 3$ and $G(n)$ be a $3$ -polytopal graph with at least one vertex of degree $i$ , for every $3\leq i\leq n$ . Then its order is at least

p(n)\geq\left\lceil\frac{n^{2}-5n+30}{6}\right\rceil.

(2.1)

Moreover, as soon as $n\geq 8$ , we also have

p(n)\geq\left\lceil\frac{n^{2}-11n+62}{4}\right\rceil.

(2.2)

Proof.

Let $p=p(n)$ , $q=q(n)$ denote order and size of $G(n)$ , and $d_{j}:=\deg(v_{j})$ . On one hand, via the handshaking lemma,

2q=\sum_{i=3}^{n}i+\sum_{j=n-1}^{p}d_{j}\geq\frac{n(n+1)}{2}-3+3(p-n+2)=\frac{(n-2)(n-3)}{2}+3p

where we used $3$ -connectivity. On the other hand, by planarity, $q\leq 3p-6$ , so that altogether

p\geq\frac{n^{2}-5n+30}{6}

hence (2.1).
By [3, 5], for any $3\leq k\leq(p+4)/3$ , it holds that

\sum_{i=1}^{k}d_{i}\leq 2p+6k-16.

(2.3)

To optimise this lower bound for $p$ , the left hand side should contain as many numbers exceeding $5$ as possible. We thus wish to take $k=n-5$ , and we may do this as long as $3\leq n-5\leq(p+4)/3$ , i.e.,

n\geq 8\quad\text{ and }\quad p\geq 3n-19.

By (2.1), these conditions certainly hold for all $n\geq 8$ . In this case, equation (2.3) with $k=n-5$ reads

\frac{n(n+1)}{2}-15\leq 2p+6(n-5)-16,

and rearranging this inequality we obtain (2.2). ∎

3 Proof of Theorem 2 for $n\leq 13$

The polyhedra up to $8$ faces were tabulated in [4] and [8]. For $4\leq n+1\leq 8$ , we are looking for polyhedra with at least one $i$ -gonal face for each $3\leq i\leq n$ . We consult [8, Table I], searching where the ‘Faces’ column has the maximal $n-2$ non-zero entries. It is straightforward to find the ten relevant cases (numbered 1, 2, 3, 4, 5, 13, 14, 15, 46, and 47 in [8]). Passing to the dual graphs, we obtain the ten $3$ -polytopes sketched in Figure 8. In particular, for $3\leq n\leq 7$ , we have $p(n)=n+1$ (cf. Table 1).

Next, we wish to find examples of polyhedra satisfying $\mathcal{P}_{n}$ for $8\leq n\leq 13$ . We observe that each graph in Figure 8, save for the tetrahedron and square pyramid, may be obtained from a previous one via a splitting operation. Our strategy is then to apply repeated splitting on the faces of $r_{7.1}$ from Figure 8, to obtain a new graph $r_{n}$ . For $8\leq n\leq 13$ , the aim is to obtain a subset of vertices of valencies $4,5,\dots,n$ . In the effort to minimise the resulting graph’s order, we split triangles of $r_{7.1}$ containing the maximal possible number of vertices of degree $4$ or more, ideally all three of them. We thereby construct the graphs of Figure 9. Their orders match the largest of the lower bounds (2.1) and (2.2) proven in section 2. We thus complete Table 1.

In the next section, we will combine the above with other ideas to write Algorithm 8, proving the cases $n\geq 14$ of Theorem 2.

4 Proof of Theorem 2 for $n\geq 14$

4.1 Setup

Let $r_{14}$ be the graph sketched in Figure 1.

Refer to caption — Figure 1: The $3$ -polytope $r_{14}$ , satisfying $\mathcal{P}_{14}$ .

It is straightforward to check that $r_{14}$ is a polyhedron, and that the respective valencies of $v_{j}$ , $1\leq j\leq 11$ , are

7,9,11,13,14,12,10,8,6,4,5.

The order of this graph is $26$ , matching the lower bound (2.2) in the case $n=14$ , and there are vertices of degree $3$ as well. Theorem 2 is hence proven in this case. In the following we recursively construct the $r_{n}$ , $n\geq 16$ , of Theorem 2. As for $r_{15}$ (Figure 10), we obtain it from $r_{14}$ via one edge deletion and again applying the ideas of section 3.

We need a preliminary definition, the operation of $\mathit{h}$ -splitting a triangle about a vertex, for some $h\geq 1$ (see Figure 2). To $h$ -split $\{a,b,c\}$ about $c$ , we begin by splitting it, introducing a new vertex $c_{1}$ . Then we split $\{a,b,c_{1}\}$ inserting $c_{2}$ , and so on, until we have added the vertex $c_{h}$ . For instance referring to Figure 8, given the tetrahedron $s_{3}$ , $1$ -splitting any face yields $s_{4.2}$ , while $2$ -splitting any face produces $s_{5.2}$ .

4.2 The case $n\equiv 2\pmod{4}$

We now describe the algorithm producing the $r_{n}$ of Theorem 2, starting from the case $n\equiv 2\pmod{4}$ . The remaining cases are covered in section 4.3.

Algorithm 8 (Part I).

Input. An integer $N\geq 16$ .

Output. A set of graphs $\{r_{n}:16\leq n\leq N\}$ , where each $r_{n}$ has property $\mathcal{P}_{n}$ .

Description. For all $k\geq 1$ , we define the graph $\text{pc}_{k}$ (‘ $k$ -th piece’) of Figure 3. The half-lines and numbers in bold represent $h$ -splitting: for instance, face $\{a_{k},b_{k},e_{k}\}$ is split $h=4k$ times about the vertex $e_{k}$ . Letting $\text{pc}_{0}:=r_{14}$ , we label $u_{0},v_{0},w_{0}$ its vertices of degrees $10,8,6$ respectively ( $v_{7},v_{8},v_{9}$ is Figure 1). The vertex (of degree $3$ ) adjacent to these three will be denoted by $x_{0}$ . Note that also in each $\text{pc}_{k}$ , $k\geq 1$ , there are vertices $u_{k},v_{k},w_{k}$ of degrees $10,8,6$ , and $x_{k}$ of degree $3$ adjacent to them. We define

r_{n}:=r_{14}\cup\bigcup_{k=1}^{(n-14)/4}\text{pc}_{k},\qquad n\geq 14,\ n\equiv 2\pmod{4},

(4.1)

identifying in each union operation the vertices $u_{k-1},v_{k-1},w_{k-1},x_{k-1}$ with $a_{k},b_{k},c_{k},d_{k}$ respectively.

Proof of Theorem 2 for $n\geq 14$ , $n\equiv 2\pmod{4}$ .

We claim that $r_{n}$ (4.1) has order (1.1) and satisfies property $\mathcal{P}_{n}$ . We argue by induction. The base case $n=14$ has already been checked. The union (4.1) is still a $3$ -polytope by construction. By the inductive hypothesis, the graph

r_{n-4}=r_{14}\cup\bigcup_{k=1}^{(n-18)/4}\text{pc}_{k}

satisfies $\mathcal{P}_{n-4}$ , and has order

p(n-4)=\frac{n^{2}-19n+132}{4}.

Turning to $r_{n}=r_{n-4}\cup\text{pc}_{(n-14)/4}$ , we record that for $\text{pc}_{k}\prec r_{n}$ , $k\geq 1$ , the vertices $a_{k},b_{k},c_{k},d_{k}$ have respective valencies

	$\displaystyle\deg_{r_{n}}(a_{k})=10+1+4k+1+2=4k+14,$
	$\displaystyle\deg_{r_{n}}(b_{k})=8+1+4k+3=4k+12,$
	$\displaystyle\deg_{r_{n}}(c_{k})=6+1+(4k-1)+2+5=4k+11,$
	$\displaystyle\deg_{r_{n}}(d_{k})=3+1+1+(4k-1)+7=4k+13.$

In particular,

	$\displaystyle\deg_{r_{n}}(a_{(n-14)/4})=n,$	$\displaystyle\deg_{r_{n}}(b_{(n-14)/4})=n-2,$
	$\displaystyle\deg_{r_{n}}(c_{(n-14)/4})=n-3,$	$\displaystyle\deg_{r_{n}}(d_{(n-14)/4})=n-1.$

The degree of the remaining vertices of $r_{n-4}$ has not changed in the union. Moreover, $\deg_{r_{n}}(u_{(n-14)/4})=10$ , $\deg_{r_{n}}(v_{(n-14)/4})=8$ , and $\deg_{r_{n}}(w_{(n-14)/4})=6$ . As for order, $\text{pc}_{(n-14)/4}$ introduces $12$ new vertices plus those given by the $h$ -splittings, namely $4(n-14)/4+2+4(n-14)/4-1=2n-27$ . It follows that

|V(r_{n})|=p(n-4)+12+2n-27=\frac{n^{2}-11n+62}{4}.

Therefore, $r_{n}$ does indeed have property $\mathcal{P}_{n}$ . Moreover, it is clear from the construction that $r_{n-4}\prec r_{n}$ . ∎

4.3 The cases $n\equiv 1,0,3\pmod{4}$

Algorithm 8 (Part II).

Continuing Algorithm 8, for $n\geq 16$ , $n\equiv 1$ (resp. $\equiv 0$ ) $\pmod{4}$ , we start by constructing $r_{n-3}$ (resp. $r_{n-2}$ ) as above. We then define

r_{n}:=r_{n-3}\cup\text{end}_{1;n}

(resp. $r_{n}:=r_{n-2}\cup\text{end}_{0;n}$ ) with $\text{end}_{1;n}$ (resp. $\text{end}_{0;n}$ ) given by Figure 4(a) (resp. 4(b)).
For $n\equiv 1$ , in the union $r_{n}:=r_{n-3}\cup\text{end}_{1;n}$ , vertices $u_{(n-17)/4},v_{(n-17)/4},w_{(n-17)/4},x_{(n-17)/4}$ are identified with $a,b,c,d$ respectively. For $n\equiv 0$ , in the union $r_{n}:=r_{n-2}\cup\text{end}_{0;n}$ , vertices $u_{(n-16)/4},v_{(n-16)/4},w_{(n-16)/4},x_{(n-16)/4}$ are identified with $\bar{a},\bar{b},\bar{c},\bar{d}$ respectively.
Finally, if $n\equiv 3\pmod{4}$ , we take

r_{n}:=r_{n-2}\cup\text{end}_{0;n}=r_{n-5}\cup\text{end}_{1;{n-2}}\cup\text{end}_{0;n},

identifying $d,v,w,x$ of $\text{end}_{1;{n-2}}$ with $\bar{a},\bar{b},\bar{c},\bar{d}$ of $\text{end}_{0;n}$ respectively.

Proof of Theorem 2 for $n\geq 16$ , $n\equiv 1,0,3\pmod{4}$ .

If $n\equiv 1$ , in $r_{n}$ one has $\deg(a)=n$ , $\deg(b)=n-1$ , and $\deg(c)=n-2$ . The remaining valencies $\geq 4$ of $r_{n-3}$ do not change in the union $r_{n}$ . Moreover, $\deg(d)=10$ , $\deg(v)=8$ , and $\deg(w)=6$ . Lastly, by Theorem 2 in the already proven case $n\equiv 2$ ,

|V(r_{n})|=p(n-3)+9+(n-11)/2+(n-13)/2+(n-15)/2=\frac{n^{2}-11n+62}{4}

as required.

Similarly, if $n\equiv 0$ , in $r_{n}$ it holds that $\deg(\bar{a})=n$ , $\deg(\bar{b})=n-1$ , $\deg(\bar{c})=10$ , $\deg(\bar{d})=8$ , and $\deg(\bar{w})=6$ . Further,

|V(r_{n})|=p(n-2)+8+(n-14)=\left\lceil\frac{n^{2}-11n+62}{4}\right\rceil.

If $n\equiv 3$ , in $r_{n}$ we have $\deg(a)=n-2$ , $\deg(b)=n-3$ , $\deg(c)=n-4$ , $\deg(\bar{a})=n$ , $\deg(\bar{b})=n-1$ , $\deg(\bar{c})=10$ , $\deg(\bar{d})=8$ , and $\deg(\bar{w})=6$ . Via the already proved case $n\equiv 1$ ,

|V(r_{n})|=p(n-2)+8+(n-14)=\left\lceil\frac{n^{2}-11n+62}{4}\right\rceil.

The relations (1.2) are clear by construction. This concludes the proof of Theorem 2. ∎

Remark 9.

The time to implement Algorithm 8 is quadratic in $n$ , and this is optimal in the sense that the order of $r_{n}$ is itself quadratic (1.1). Moreover, constructing $r_{N}$ takes no more time than obtaining all of

r_{14},r_{18},\dots,r_{N-(N\mod 4+2)},r_{N}

(cf. (1.2)).

5 Another application

The ideas of the preceding sections have solved the problem of finding for all $n$ a graph satisfying $\mathcal{P}_{n}$ of Definition 1. The following lemma constitutes an application of the same ideas, and it illustrates how a minor modification of Algorithm 8 allows to answer similar questions. Moreover, the result of the lemma will be needed in section 6.

Lemma 10.

Let $n\geq 17$ , $n\equiv 1\pmod{4}$ , and $H$ be an order $p$ polyhedral graph with at least one vertex of degree $i$ , $3\leq i\leq n$ , and at least three vertices of degree $n-1$ . Then its minimal order is

\frac{n^{2}-7n+34}{4}.

(5.1)

Proof.

Let us show the lower bound first. Similarly to Lemma 7, we begin by imposing

6p-12\geq n+3(n-1)+\frac{(n-2)(n-1)}{2}-3+\sum_{j=n}^{p}d_{j}\geq\frac{n^{2}-n-10}{2}+3p,

leading to

p\geq\frac{n^{2}-n+14}{6}.

Thereby, for $n\geq 17$ , we certainly have $3\leq n-4\leq(p+4)/3$ . Applying (2.3) with $k=n-4$ yields the inequality

n+3(n-1)+\frac{(n-2)(n-1)}{2}-21\leq 2p+6(n-4)-16,

and rearranging this inequality and imposing $n\equiv 1\pmod{4}$ we obtain (5.1) as a lower bound.

To show the upper bound, we will actually construct a graph $s_{n}$ satisfying the assumptions of the present lemma, of order (5.1). We set

s_{n}:=r_{n}\cup\text{end}^{\prime}_{n}\qquad n\geq 17,\ n\equiv 1\pmod{4}

(5.2)

where $r_{n}$ was constructed in Algorithm 8 and $\text{end}^{\prime}_{n}$ is depicted in Figure 5.

Since $n\equiv 1\pmod{4}$ ,

s_{n}=r_{n-3}\cup\text{end}_{1;n}\cup\text{end}^{\prime}_{n}.

While performing the union, we identify vertices $d,v,w,x$ of $\text{end}_{1;n}$ (Figure 4(a)) with $a^{\prime},b^{\prime},c^{\prime},d^{\prime}$ of $\text{end}^{\prime}_{n}$ in this order. Then $s_{n}$ is clearly still a polyhedron. Further, $\deg_{s_{n}}(a^{\prime})=10+2+n-13=n-1$ , $\deg_{s_{n}}(b^{\prime})=8+4+n-13=n-1$ , $\deg_{s_{n}}(c^{\prime})=6+4=10$ , $\deg_{s_{n}}(d^{\prime})=3+5=8$ , and $\deg_{s_{n}}(w^{\prime})=6$ . Since $r_{n}$ has the property $\mathcal{P}_{n}$ , then $s_{n}$ has vertices of each degree $i$ , $3\leq i\leq n$ . The union with $\text{end}^{\prime}_{n}$ has inserted two more vertices of valency $n-1$ . Lastly,

|V(s_{n})|=|V(r_{n})|+6+(n-13)=\frac{n^{2}-11n+62+4n-28}{4}=\frac{n^{2}-7n+34}{4}.

(5.3)

The proof of Lemma 10 is complete. ∎

Remark 11.

We record the following property of the graph $s_{n}$ . It plainly has degree $3$ vertices, and contains among its faces the triangles

F_{n;j}=\{v_{n;j;1},v_{n;j;2},v_{n;j;3}\},\quad 1\leq j\leq(n-1)/2

(5.4)

where $\deg(v_{n;1;1})=\deg(v_{n;1;2})=n-1$ ,

\{\deg(v_{n;j;1}):2\leq j\leq(n-1)/2\}\cup\{\deg(v_{n;j;2}):2\leq j\leq(n-1)/2\}=\{4,5,\dots,n\}

and

v_{n;j;3}\neq v_{n;i;1},v_{n;i;2},\quad\forall j,i.

This property, stronger than $\mathcal{Q}_{n}$ of Definition 3, shall be denoted by $\mathcal{R}_{n}$ . Indeed for $s_{n}$ , $\mathcal{R}_{n}$ is easily observed by construction. For instance, we may take the pairs

	$\displaystyle(7,4),(13,12),(9,5),(14,11),$
	$\displaystyle(4k+14,4k+12),(4k+11,4k+13)\quad\text{ for }1\leq k\leq(n-17)/4,$
	$\displaystyle(n,n-1),(n-2,10),(n-1,n-1),(8,6)$

where the notation $(a,b)$ means that if $u,v$ denote two vertices of one of the triangles $F_{n;j}$ , then $\deg(u)=a$ and $\deg(v)=b$ .

6 Proof of Theorem 4

6.1 Premise

We first introduce the main ideas of the proof, via the following lemma.

Lemma 12.

Let $t_{l}$ be as in Theorem 4. Then we may construct a sequence of $3$ -polytopes

\{t_{n}\}_{n=l+2k,\ k\geq 1},

where $t_{l+m(k-1)}\prec t_{l+mk}$ for $k\geq 1$ , and each $t_{n}$ satisfies $\mathcal{Q}_{n}$ . Moreover along the sequence, for all $\epsilon>0$ , one has

|V(t_{n})|\leq\frac{n^{2}}{4}+\left(-1+\epsilon\right)n

(6.1)

as $n\to\infty$ .

Here we prove the first statement, relegating the proof of the second one (6.1) to section 6.3. The base case is just the assumption of the lemma. We take the inductive hypothesis that $t_{l+2(k-1)}$ verifies property $\mathcal{Q}_{l+2(k-1)}$ of Definition 3. Suppose that at step $k$ , $1\leq k\leq N$ , we were to perform $2$ -splitting on each triangle

F_{l+2(k-1);j},\quad 1\leq j\leq(l+2(k-1)-3)/2

(1.3) about vertex $v_{l+2(k-1);j;3}$ . That would raise by $2$ the degrees of a set of vertices of valencies $4,5,\dots,l+2(k-1)$ . However, in the resulting graph, we would not be guaranteed vertices of degrees $4$ and $5$ . Therefore, the $2$ -splitting is taken only for

2\leq j\leq(l+2(k-1)-3)/2

(i.e., all these faces save $F_{l+2(k-1);1}$ ). We replace $F_{l+2(k-1);1}$ with the graph $S$ of Figure 6, identifying $v_{l+2(k-1);1;1},v_{l+2(k-1);1;2},v_{l+2(k-1);1;3}$ with $a,b,c$ respectively.

In this way, the valencies of $v_{l+2(k-1);1;1}$ and $v_{l+2(k-1);1;2}$ increase by $2$ , and they belong to the new triangle $F_{l+2k;(l+2k-3)/2}:=\{a,b,g\}$ . Two vertices of valencies $4$ and $5$ are introduced, namely $d,e$ . Moreover, these two belong to a triangle $F_{l+2k;1}:=\{d,e,f\}$ . We also set

F_{l+2k;j}:=\{v_{l+2(k-1);j;1},v_{l+2(k-1);j;2},v_{l+2(k-1);j;3}^{\prime\prime}\},\qquad 2\leq j\leq(l+2k-3)/2-1

where $v_{l+2(k-1);j;3}^{\prime\prime}$ is the second of the two vertices introduced in the $2$ -splitting of $F_{l+2(k-1);j}$ . We have thus constructed $t_{l+2k}$ satisfying $\mathcal{Q}_{l+2k}$ as claimed.

In section 6.3, it will be shown that the above produces a sequence of graphs $t_{n}$ verifying (6.1). Our goal is to optimise this method to asymptotically improve this upper bound on $|V(t_{n})|$ .

6.2 The algorithm

In section 6.1 we have used the polyhedron $S$ as it has the $2$ triangles $\{a,b,g\}$ and $\{d,e,f\}$ , with vertices of appropriate valencies $\deg(d)=5$ and $\deg(e)=\deg(a)=\deg(b)=4$ . A refinement of this idea is then to pick $m$ even and use in place of $S$ a polyhedron containing $(m+2)/2$ triangles, where two vertices from each form a set of vertices of degrees

m+3,m+2,m+2,m+2,m+1,m,m-1,\dots,5,4.

We have seen in Remark 11 that for $m\geq 14$ , $s_{m+3}$ has the desired property $\mathcal{R}_{m+3}$ .

Algorithm 13.

Input. A $3$ -polytopal graph $t_{l}$ satisfying $\mathcal{Q}_{l}$ , an integer $m\geq 14$ , $m\equiv 2\pmod{4}$ , and a positive integer $N$ .

Output. A set of graphs $\{t_{n}=t_{l+mk}:1\leq k\leq N\}$ , each satisfying property $\mathcal{Q}_{n}$ , and $t_{l+m(k-1)}\prec t_{l+mk}$ . These are the first $N$ entries of a sequence verifying (1.5).

Description. Starting from $t_{l}$ , we perform steps $1\leq k\leq N$ as follows. The graph $t_{l+m(k-1)}$ verifies $\mathcal{Q}_{l+m(k-1)}$ , i.e. it has $(l+m(k-1)-3)/2$ triangular faces

F_{l+m(k-1);j}=\{v_{l+m(k-1);j;1},v_{l+m(k-1);j;2},v_{l+m(k-1);j;3}\},\quad 1\leq j\leq(l+m(k-1)-3)/2

where

\{\deg(v_{l+m(k-1);j;1}):1\leq j\leq(l+m(k-1)-3)/2\}\ \\ \cup\ \{\deg(v_{l+m(k-1);j;2}):1\leq j\leq(l+m(k-1)-3)/2\}=\{4,5,\dots,l+m(k-1)\}.

At step $k$ , we $m$ -split the $F_{l+m(k-1);j}$ about $v_{l+m(k-1);j;3}$ , for $j=2,\dots,(l+m(k-1)-3)/2$ . Next, we replace the remaining triangle $F_{l+m(k-1);1}$ with a copy of $s_{m+3}$ from Lemma 10, identifying $v_{l+m(k-1);1;1}$ and $v_{l+m(k-1);1;2}$ with two adjacent vertices of degree $m+2$ in $s_{m+3}$ . This is well defined, since $m+3\geq 17$ , $m+3\equiv 1\pmod{4}$ , and $s_{m+3}$ has property $\mathcal{R}_{m+3}$ (Remark 11). In this way, we have increased by $m$ the degrees of a set of vertices of valencies $4,5,\dots,l+m(k-1)$ , and we have introduced $m$ new vertices of degrees $\{4,5,\dots,m+3\}$ (applying Lemma 10). Moreover, these new vertices, together with $v_{l+m(k-1);1;1}$ and $v_{l+m(k-1);1;2}$ , belong pairwise to $(m+2)/2$ triangles, by the construction of $s_{m+3}$ (Remark 11). We have thus obtained $t_{l+mk}$ satisfying $\mathcal{Q}_{l+mk}$ . Relation (1.6) follows by construction.

6.3 Concluding the proofs of Theorem 4 and Lemma 12

It remains to show (1.5). In Algorithm 13, starting with $|V(t_{l})|$ vertices, at step $k\geq 1$ we have inserted $m$ of them for each of $(l-3+m(k-1))/2-1$ $m$ -splittings, plus $|V(s_{m+3})|-3$ for the operation on $F_{l+m(k-1);1}$ (i.e. replacing this triangle with a copy of $s_{m+3}$ ). Therefore,

	$\displaystyle\|V(t_{n})\|$	$\displaystyle=\|V(t_{l})\|+\sum_{k=1}^{(n-l)/m}\left[m\cdot\frac{l-5+m(k-1)}{2}+\|V(s_{m+3})\|-3\right]$
		$\displaystyle=\|V(t_{l})\|+\frac{m^{2}}{2}\sum_{k=1}^{(n-l)/m}(k-1)+\frac{m(l-5)}{2}\cdot\frac{n-l}{m}+(\|V(s_{m+3})\|-3)\cdot\frac{n-l}{m}$
		$\displaystyle\leq\frac{n^{2}}{4}+\left(\frac{4\|V(s_{m+3})\|-m^{2}-10m-12}{4m}+\epsilon\right)n,$

where as $n\to\infty$ we have bounded the constant terms via $\epsilon n$ , for all $\epsilon>0$ . Substituting the value (5.1), we have as $n\to\infty$

|V(t_{n})|\leq\frac{n^{2}}{4}+\left(\frac{-11m+10}{4m}+\epsilon\right)n

as required. The proof of Theorem 4 is complete.

Note that $m$ was chosen so that $m+3\geq 17$ and $m+3\equiv 1\pmod{4}$ hold, in order to minimise the quantity

\frac{4|V(s_{m+3})|-m^{2}-10m-12}{4m}

(Lemma 10) so that ultimately the coefficient of $n$ in (1.5) is as small as this method allows.

In Lemma 12, we had fixed instead $m=2$ , and used the graph $S$ (Figure 6) in place of $s_{m+3}$ . Since $|V(S)|=7$ , we get (6.1). This concludes the proof of Lemma 12.

Future directions.

The ideas behind Algorithms 8 and 13 are readily generalisable to tackle problems of a similar flavour, as shown for instance in section 5. The constructions, or a slight modification thereof, allow to minimise the total number of vertices of a graph, where certain valencies have been fixed.

Appendix A Another way to present Algorithm 8

The following construction of $r_{n}$ may be more intuitive than Algorithm 8, albeit less apt for implementation. We begin by fixing $n\geq 9$ and defining a polyhedron $A(n)$ of order $n-5$ as follows. Given an initial triangle $\{v_{1},v_{2},v_{3}\}$ , we add in order $v_{4},v_{5},\dots,v_{n-5}$ together with edges

v_{i}v_{i-1},\quad v_{i}v_{i-2},\quad v_{i}v_{i-3},\qquad i=4,5,\dots,n-5

(splitting operations). The resulting $A(n)$ for $n=14,21$ are illustrated in Figure 7.

We note that $A(9)\cong r_{3}$ , $A(10)\cong r_{4.2}$ , $A(11)\cong r_{5.2}$ , and $A(12)\cong r_{6.3}$ from Figure 8. For all $n\geq 11$ , the degree sequence of these graphs is

3,4,5,6^{n-11},5,4,3

where the superscript is a shorthand indicating quantities of repeated numbers, e.g. $6^{n-11}$ means $n-11$ vertices of degree $6$ .

Assuming $n\geq 14$ , we pass from $A(n)$ to another polyhedron $B(n)$ in the following way. Firstly, we apply the splitting operation to every face of $A(n)$ . This has the effect of doubling all previous vertex degrees, and introducing $2(n-5)-4$ new ones ( $A(n)$ is a triangulation – it is maximal planar) so that the sequence is now

6,8,10,12^{n-11},10,8,6,3^{2n-14}.

Secondly, we split either of the two faces containing $v_{1},v_{4}$ . This yields in particular a vertex of degree $4$ . To obtain one of degree $5$ , we split the two faces that are adjacent to one another and that contain $v_{2},v_{5}$ and $v_{3},v_{5}$ respectively. For instance, in Figure 1, inserting $v_{24}$ raises the valency of $v_{10}$ to $4$ , and inserting $v_{25},v_{26}$ raises the valency of $v_{11}$ to $5$ . The constructed polyhedron shall we denoted by $B(n)$ . Its order is

|V(B(n))|=(n-5)+(2(n-5)-4)+3=3n-16,

(A.1)

and its sequence

7,9,11,13,14,12,12^{n-14},10,8,6,5,4,3^{2n-13}.

(A.2)

In (A.2), we have purposefully isolated a subset of vertices of degree $12$

V^{\prime}:=V^{\prime}(B(n))\subset V(B(n)),

(A.3)

with cardinality $n-14$ , keeping the remaining one aside.

We have $B(14)\cong r_{14}$ (Figure 1). For $n\geq 16$ our strategy is outlined as follows. The vertices in $A(n)$ have been designated to eventually correspond to ones of degree $6$ or higher in $r_{n}$ . Following the ideas of section 3, $B(n)$ has been constructed by splitting faces of $A(n)$ that contain three of these vertices of high degree. Next, starting from $B(n)$ , we split faces containing two of them. We take four vertices from $V^{\prime}$ of (A.3). Via nine repeated splitting operations, we aim to raise their degrees to $15,16,17,18$ . Similarly, the next four shall become of degrees $19,20,21,22$ , and so forth $4k+11,4k+12,4k+13,4k+14$ . This procedure ends when there remain either $2,3,0$ , or $5$ vertices in $V^{\prime}$ , depending on whether $n\equiv 0,1,2$ , or $3\pmod{4}$ . For $n\equiv 2$ the algorithm stops here. In the other cases $n\equiv 0,1,3$ , we look to apply further triangle splittings, to obtain vertices of degrees

n-1,n,\qquad n-2,n-1,n,\qquad\text{ or }\ n-4,n-3,n-2,n-1,n

respectively. The details have already been presented in section 4.

Appendix B Illustrations for small cases of Theorem 2

Here we sketch certain $3$ -polytopes mentioned in sections 3 and 4.

(a)

r_{3}

(b)

r_{4.1}

(c)

r_{4.2}

(d)

r_{5.1}

(e)

r_{5.2}

(f)

r_{6.1}

(g)

r_{6.2}

(h)

r_{6.3}

(i)

r_{7.1}

(j)

r_{7.2}

Figure 8: The

10

polyhedra with

p(n)=n+1

References

[1] David Barnette. On $p$ -vectors of $3$ -polytopes. Journal of Combinatorial Theory, 7(2):99–103, 1969.
[2] David Barnette, Peter Gritzmann, and Rainer Höhne. On valences of polyhedra. Journal of Combinatorial Theory, Series A, 58(2):279–300, 1991.
[3] Robert Bowen. On sums of valencies in planar graphs. Canadian Mathematical Bulletin, 9(1):111–114, 1966.
[4] Doyle Britton and Jack David Dunitz. A complete catalogue of polyhedra with eight or fewer vertices. Acta Crystallographica Section A: Crystal Physics, Diffraction, Theoretical and General Crystallography, 29(4):362–371, 1973.
[5] Vašek Chvátal. Planarity of graphs with given degrees of vertices. Nieuw Arch. Wisk, 3(17):47–60, 1969.
[6] Reinhard Diestel. Graph theory 3rd ed. Graduate texts in mathematics, 173, 2005.
[7] Victor Eberhard. Zur morphologie der polyeder: mit vielen figuren im text. BG Teubner, 1891.
[8] PJ Federico. Polyhedra with 4 to 8 faces. Geometriae Dedicata, 3(4):469–481, 1975.
[9] JC Fisher. An existence theorem for simple convex polyhedra. Discrete Mathematics, 7(1-2):75–97, 1974.
[10] Branko Grünbaum. Some analogues of Eberhard’s theorem on convex polytopes. Israel journal of mathematics, 6(4):398–411, 1968.
[11] Frank Harary. Graph theory. Addison-Wesley, 1991.
[12] AF Hawkins, AC Hill, JE Reeve, and JA Tyrrell. On certain polyhedra. The Mathematical Gazette, 50(372):140–144, 1966.
[13] Stanislav Jendrol. On face vectors and vertex vectors of convex polyhedra. Discrete mathematics, 118(1-3):119–144, 1993.
[14] Stanislav Jendrol. On face-vectors and vertex-vectors of polyhedral maps on orientable $2$ -manifolds. Mathematica Slovaca, 43(4):393–416, 1993.
[15] EF Schmeichel and SL Hakimi. On planar graphical degree sequences. SIAM Journal on Applied Mathematics, 32(3):598–609, 1977.

	$\displaystyle\|V(t_{n})\|$	$\displaystyle=\|V(t_{l})\|+\sum_{k=1}^{(n-l)/m}\left[m\cdot\frac{l-5+m(k-1)}{2}+\|V(s_{m+3})\|-3\right]$
		$\displaystyle=\|V(t_{l})\|+\frac{m^{2}}{2}\sum_{k=1}^{(n-l)/m}(k-1)+\frac{m(l-5)}{2}\cdot\frac{n-l}{m}+(\|V(s_{m+3})\|-3)\cdot\frac{n-l}{m}$
		$\displaystyle\leq\frac{n^{2}}{4}+\left(\frac{4\|V(s_{m+3})\|-m^{2}-10m-12}{4m}+\epsilon\right)n,$

CONSTRUCTING CERTAIN FAMILIES OF 𝟑\mathbf{3}-POLYTOPAL GRAPHS

Abstract

1 Introduction

1.1 The question

Definition 1.

Theorem 2.

Theorem 2’.

1.2 A related problem

Definition 3.

Theorem 4.

Remark 5.

Remark 6.

1.3 Related literature, notation, and plan of the paper

Related literature.

Notation.

Plan of the paper.

1.4 Acknowledgements

2 The lower bound

Lemma 7.

Proof.

3 Proof of Theorem 2 for n≤13n\leq 13

4 Proof of Theorem 2 for n≥14n\geq 14

4.1 Setup

4.2 The case n≡2(mod4)n\equiv 2\pmod{4}

Algorithm 8 (Part I).

Proof of Theorem 2 for n≥14n\geq 14, n≡2(mod4)n\equiv 2\pmod{4}.

4.3 The cases n≡1,0,3(mod4)n\equiv 1,0,3\pmod{4}

Algorithm 8 (Part II).

Proof of Theorem 2 for n≥16n\geq 16, n≡1,0,3(mod4)n\equiv 1,0,3\pmod{4}.

Remark 9.

5 Another application

Lemma 10.

Proof.

Remark 11.

6 Proof of Theorem 4

6.1 Premise

Lemma 12.

6.2 The algorithm

Algorithm 13.

6.3 Concluding the proofs of Theorem 4 and Lemma 12

Future directions.

Appendix A Another way to present Algorithm 8

Appendix B Illustrations for small cases of Theorem 2

References

CONSTRUCTING CERTAIN FAMILIES OF $\mathbf{3}$ -POLYTOPAL GRAPHS

3 Proof of Theorem 2 for $n\leq 13$

4 Proof of Theorem 2 for $n\geq 14$

4.2 The case $n\equiv 2\pmod{4}$

Proof of Theorem 2 for $n\geq 14$ , $n\equiv 2\pmod{4}$ .

4.3 The cases $n\equiv 1,0,3\pmod{4}$

Proof of Theorem 2 for $n\geq 16$ , $n\equiv 1,0,3\pmod{4}$ .