Constructing certain families of 3‐polytopal graphs

Letn ≥ 3 $n\ge 3$ andR n${R}_{n}$ be a 3‐polytopal graph such that for every3 ≤ i ≤ n $3\le i\le n$ ,R n${R}_{n}$ has at least one vertex of degreei $i$ . We find the minimal vertex count forR n${R}_{n}$ . We then describe an algorithm to construct the graphsR n${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‐polytopeT l${T}_{l}$ comprising a vertex of degreei $i$ for all3 ≤ i ≤ l $3\le i\le l$ ,l $l$ fixed, we define an algorithm to output forn > l $n\gt l$ a 3‐polytopeT n${T}_{n}$ comprising a vertex of degreei $i$ , for all3 ≤ i ≤ n $3\le i\le n$ , and such that the initialT l${T}_{l}$ is a subgraph ofT n${T}_{n}$ . The vertex count ofT n${T}_{n}$ is asymptotically optimal, in the sense that it matches the aforementioned minimal vertex count up to order of magnitude, asn $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.