Past exam of the mathematics course of the University of Cambridge / 2019 / ii / Paper 3 / 17G (Graph Theory)

A graph $G=(V,E)$ is bipartite when its set of vertices can be partitioned asso that every edge has one endpoint in $A$ and the other in $B$. Equivalently, $G$ has a proper graph colouring with at most two colours.

Suppose first that $G$ is bipartite. As one traverses any cycle in a graph, its vertices alternate between the two vertex classes. Returning to the initial class therefore requires an even number of edges, so $G$ contains no odd cycle.

Conversely, suppose that $G$ has no odd cycle. Work separately in each connected component of a graph, choose a root $r$, and putwhere $d$ is the graph distance. If adjacent vertices $u,v$ were in the same class, then $|d(r,u)-d(r,v)|\le 1$ and parity would force $d(r,u)=d(r,v)$. Choose a breadth-first spanning tree. The two tree paths from $r$ to $u$ and $v$ diverge at some last common vertex; their remaining segments have equal length, and adjoining the edge $uv$ gives an odd cycle. This contradiction shows that every edge joins $A$ to $B$, proving the odd-cycle characterization of bipartite graphs.

The Erdős-Stone theorem states precisely that, for every fixed graph $H$ with chromatic number $\chi (H)\ge 2$,If the bipartite graph $G$ has an edge, then $\chi (G)=2$. Substitution into the theorem givesIf $G$ has no edges, then every graph of sufficiently large order contains $G$ as a subgraph, so the conclusion is immediate.

For each edge $e$, let $I_e$ be the indicator random variable of the event that precisely one endpoint lies in $U$. Independent inclusion of the two endpoints with probability $1/2$ givesBecause $X={\sum }_{e\in E(G)}{I}_e$, linearity of expectation givesSome realization therefore has $X\ge m/2$. Retaining its crossing edges gives a subgraph that is bipartite, with vertex classes $U$ and $V(G)\setminus U$, proving the random cut lower bound.

Now suppose $n$ is an even number and instead choose $U$ uniformly among all subsets of size $n/2$. For a fixed edge $uv$,and the reverse orientation has the same probability. ThusAnother application of linearity of expectation givesAt least one such balanced choice attains this expectation, and its crossing edges give the required subgraph that is bipartite. This is the balanced random cut lower bound.