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

Colour every vertex of a graph independently and uniformly with three colours, and retain precisely the edges whose endpoints have different colours. Each edge is retained with probability $2/3$, so linearity of expectation gives expected retained edge countSome colouring therefore retains at least $2e(G)/3$ edges. Its retained subgraph is three-colourable, and deleting edges if necessary leaves exactlyedges without increasing its chromatic number. This is the three-colourable two-thirds subgraph lemma.

To prove sharpness, take $G=K_n$. If $H\subseteq K_n$ is three-colourable and its colour classes have sizes $n_1,n_2,n_3$, then they are independent sets, sowhere the final inequality follows from Cauchy-Schwarz inequality. Since $e(K_n)=n(n-1)/2$,Given $\epsilon >0$, choose $n$ with $2/[3(n-1)]\le \epsilon$. Then every three-colourable subgraph has at most $(2/3+\epsilon )e(G)$ edges.

Choose a partition $V=A\bigsqcup B$ that maximizes the number of edges crossing between its two parts. If some $v\in A$ hadmoving $v$ to $B$ would replace the former crossing edges incident with $v$ by the latter and strictly increase the cut size. This contradicts maximality. The same argument applies to every $v\in B$. Hence every vertex has at least as many neighbours in the opposite part as in its own part, so the maximum cut is an unfriendly partition of a graph.

Enumerate the vertices as $v_1,v_2,\dots$. Since every vertex has finite degree, choose increasing finite vertex sets $W_n$ whose union is $V$ and such that the closed neighbourhood of $v_i$ lies in $W_n$ whenever $i\le n$. By part (b), each finite induced graph $G[W_n]$ has an unfriendly two-colouring.

There are only two colours. Pass successively to an infinite subsequence on which the colour of $v_1$ is constant, then one on which the colour of $v_2$ is constant, and so on. The diagonal argument gives a limiting colouring in which, for every fixed finite set of vertices, all its colours agree with those in infinitely many of the finite colourings.

Fix $v_i$. Its entire finite neighbourhood lies in every sufficiently large $W_n$, and along the diagonal subsequence the colours of $v_i$ and all its neighbours eventually stabilize. The unfriendly inequality for $v_i$ in $G[W_n]$ therefore passes unchanged to the limit. This holds for every vertex, proving the unfriendly partition theorem for a countable locally finite graph.

Colour every vertex independently red or blue with probability $1/2$. Fix a vertex $v$ and enumerate infinitely many distinct neighbours $w_1,w_2,\dots$. The probability that all neighbours after $w_n$ are red isTaking the countable union over $n$, the probability that $v$ has only finitely many blue neighbours is zero. The same argument with the colours exchanged shows that the probability of only finitely many red neighbours is zero.

The vertex set is countable, so the union of these two null events over all vertices still has probability zero. Thus with probability one every vertex has infinitely many neighbours of each colour. Taking $A$ and $B$ to be the two colour classes gives an unfriendly partition. This is the random unfriendly partition of a countable infinite-degree graph.