Cubic graphs whose average number of regions is small (Q1126220): Difference between revisions

\textit{D. Archdeacon} [Congr. Numerantium 67, 114-124 (1988; Zbl 0669.05027)] asked whether, for connected cubic graphs \(G\), the average number of regions in a random orientable imbedding of \(G\) (i.e. the expected number of regions, for the uniform distribution) is roughly a linear function of the order of \(G\). The present paper answers this question in the negative, by showing that, for every even \(n\) large enough, there is a connected cubic graph \(G_n\) of order \(n\) for which \(r_{\text{avg}}(G_n)<1+\ln(n+2)\). The proof is existential; no large cubic graphs are known having this scarcity of regions. Numerical evidence is given for the conjecture that complete graphs have a similar logarithmic bound.