Let $G$ be a graph with $n$ vertices and $m$ edges. Show that if $G$ contains no $C_{4}$, then $m \leqslant \frac{n}{4}(1+\sqrt{4 n-3})$.

Let $C_{4}(G)$ denote the number of subgraphs of $G$ isomorphic to $C_{4}$. Show that if $m \geqslant \frac{n(n-1)}{4}$, then $G$ contains at least $\frac{n(n-1)(n-3)}{8}$ paths of length 2 . By considering the numbers $r_{1}, r_{2}, \ldots, r_{\left(\begin{array}{c}n \\ 2\end{array}\right)}$ of vertices joined to each pair of vertices of $G$, deduce that

$$C_{4}(G) \geqslant \frac{1}{2}\left(\begin{array}{l} n \\ 2 \end{array}\right)\left(\begin{array}{c} (n-3) / 4 \\ 2 \end{array}\right)$$

Now let $G=G(n, 1 / 2)$ be the random graph on $\{1,2, \ldots, n\}$ in which each pair of vertices is joined independently with probability $1 / 2$. Find the expectation $\mathbb{E}\left(C_{4}(G)\right)$ of $C_{4}(G)$. Deduce that if $0<\epsilon<1 / 2$, then

$$\operatorname{Pr}\left(C_{4}(G) \leqslant(1+2 \epsilon) \frac{3}{16}\left(\begin{array}{l} n \\ 4 \end{array}\right)\right) \geqslant \epsilon$$