Graphs without four-cycle
Task number: 3899
Prove that for an infinite number of different \(n\) there are graphs on \(n\) vertices with \(\Omega(n^{3/2})\) edges which do not contain a four-cycle \(C_4\) as a subgraph.
You can elegantly use finite projective planes for the construction.
Solution
Observe that the projective plane incidence graph cannot contain the four-cycle \( a, P, b, Q \), because this would mean that the lines \(P\) and \( Q \) intersect at two points.
If \( G \) is the graph of the incidence of the projective plane of the order \(k\), the \(|V_G|=n=2k^2+2k+2\) and \(|E_G|=(k^2+k+1)(k+1)\). Since \((k+1)^2>k^2+k+1\), we get \(|E_G|\ge \frac{n}2 \sqrt{\frac{n}2}=2^{-3/2}n^{3/2}\).
