(a) What does it mean to say that a graph is bipartite?

(b) Show that $G$ is bipartite if and only if it contains no cycles of odd length.

(c) Show that if $G$ is bipartite then

$$\frac{\operatorname{ex}(n ; G)}{\left(\begin{array}{l} n \\ 2 \end{array}\right)} \rightarrow 0$$

as $n \rightarrow \infty$.

[You may use without proof the Erdós-Stone theorem provided it is stated precisely.]

(d) Let $G$ be a graph of order $n$ with $m$ edges. Let $U$ be a random subset of $V(G)$ containing each vertex of $G$ independently with probability $\frac{1}{2}$. Let $X$ be the number of edges with precisely one vertex in $U$. Find, with justification, $\mathbb{E}(X)$, and deduce that $G$ contains a bipartite subgraph with at least $\frac{m}{2}$ edges.

By using another method of choosing a random subset of $V(G)$, or otherwise, show that if $n$ is even then $G$ contains a bipartite subgraph with at least $\frac{m n}{2(n-1)}$ edges.