The Minimum Number of $4$-Cycles in a Maximal Planar Graph with Small Number of Vertices

Abstract

Hakimi and Schmeichel determined a sharp lower bound for the number of cycles of length 4 in a maximal planar graph with $n$ vertices, $n\ge 5$. It has been shown that the bound is sharp for $n=5,12$ and $n\ge 14$ vertices. However, the authors only conjectured the minimum number of cycles of length 4 for maximal planar graphs with the remaining small vertex numbers. In this note, we confirm their conjecture.

arXiv comment9 pages, 7 figures