The Maximum Size of $C_4$-Free Planar Graphs

Abstract

A planar graph is called $C_4$-free if it has no cycles of length four. Let $f(n,C_4)$ denote the maximum size of a $C_4$-free planar graph with order $n$. In this paper, it is shown that $f(n,C_4)=\lfloor \frac{15}{7}(n-2)\rfloor –\mu$ for $n\ge 30$, where $\mu =1$ if $n\equiv 3(\mathrm{mod}7)$ or $n=32,33,37$, and $\mu =0$ otherwise.