An Extremal Characterization of the Incidence Graphs of Projective Planes

摘要

Let G be a 4-cycle free, bipartite graph on 2n vertices with partitions of equal cardinality n. Let c_6(G) denote the number of cycles of length 6 in G. We prove that for n ≥ 3, c_6(G) ≤ 1/3(_2~n)(n - r_n), where r_n = 1/2 + 4n-3~(1/2)/2, with equality if and only if G is the incidence point-line graph of a projective plane.