An Extremal Characterization of Projective Planes

Abstract

In this article, we prove that amongst all $n$ by $n$ bipartite graphs of girth at least six, where $n = q^2 + q + 1 \ge 157$, the incidence graph of a projective plane of order $q$, when it exists, has the maximum number of cycles of length eight. This characterizes projective planes as the partial planes with the maximum number of quadrilaterals.