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}\).

Difficulty level: Easy task (using definitions and simple reasoning)
Reasoning task
Cs translation
Send comment on task by email