4‐valent graphs
T.C. Enns · Journal of Graph Theory · 1982
Abstract Let { p k } k ≥2, k ≠4 be a sequence of non‐negative integers which satisfies 8 + Σ k ≥3 ( k — 4) p k = 0. Then there exists an integer p 4 such that there exists a 2‐connected planar graph with exactly p k k ‐gons as faces for all k ≥ 2. This paper determines all such p 4 when p k = 0 for k ≥ 5 and determines that there is a constant C ≥ 1 such that for some m ≤ p 2 + 1/4 p 3 + C , there exists a 2‐connected planar graph with exactly p k faces for each p 4 = m + 2 w , w a positive integer. When there exists at least one odd k ≥ 3 for which p k ≠ 0, the coefficient 2 of w in the above equation may be replaced by 1. These conclusions do not hold if the coefficients of p 2 and p 3 are any smaller than 1 and 1/4, respectively.