Past exam of the mathematics course of the University of Cambridge / 2019 / iii / Paper 147 / 1 / i

For $x_1,x_2\in X$, let $d(x_1,x_2)$ be the number of vertices of $Y$ adjacent to both. The required number $Q$ of ordered quadruples isThe Cauchy-Schwarz inequality first givesReverse the order of counting. A vertex $y\in Y$ contributes $\mathrm{deg}(y{)}^2$ ordered pairs, so a second application of Cauchy-Schwarz and the assumed edge density of a bipartite graph giveTherefore the bipartite four-cycle count is