Proof. We want to show that if $G$ is a bipartite graph of density $\alpha$ with vertex sets $X,Y$ of size $m$ and $n$ and we choose $x_1,x_2\in X$, $y_1,y_2\in Y$ independently at random, then

$$\mathbb{P}[x_1{y}_2,x_2{y}_1,x_2{y}_2\in E(G)]\ge {\alpha }^3.$$

It would be enough to let $P$ be a P3 chosen uniformly at random and show that $H[P]\ge \log ({\alpha }^3{m}^2{n}^2)$.

Instead we shall define a different random variable taking values in the set of all P3s (and then apply maximality).

To do this, let $(X_1,Y_1)$ be a random edge of $G$ (with $X_1,\in X$, $Y_1\in Y$). Now let $X_2$ be a random neighbour of $Y_1$ and let $Y_2$ be a random neighbour of $X_2$.

It will be enough to prove that

$$H[X_1,Y_1,X_2,Y_2]\ge \log ({\alpha }^3{m}^2{n}^2).$$

We can choose $X_1{Y}_1$ in three equivalent ways:

• (1) Pick an edge uniformly from all edges.
• (2) Pick a vertex $x$ with probability proportional to its degree $d(x)$, and then pick a random neighbour $y$ of $x$.
• (3) Same with $x$ and $y$ exchanged.

It follows that $Y_1=y$ with probability $\frac{d(y)}{|E(G)|}$, so $X_2{Y}_1$ is uniform in $E(G)$, so $X_2=x^{\prime }$ with probability $\frac{d(x^{\prime })}{|E(G)|}$, so $X_2{Y}_2$ is uniform in $E(G)$.

Therefore,

So we are done my maximality.

Alternative finish (to avoid using $\log$!):

Let $X^{\prime },Y^{\prime }$ be uniform in $X,Y$ and independent of each other and $X_1,Y_1,X_2,Y_2$. Then:

$$\begin{array}{llll}\hfill H[X_1,Y_2,X_2,Y_2,X^{\prime },Y^{\prime }]& =H[X_1,Y_1,X_2,Y_2]+H[U_X]+H[U_Y]& \hfill & \\ \hfill & \ge 3H[U_{E(G)}]& \hfill & \end{array}$$

So by maximality,

$$\#P_{3}s\times |X|\times |Y|\ge |E(G){|}^3.\square$$