Cut of a graph

A cut is a partition $V=A\bigsqcup B$ of the vertex set. Its size is the number of edges with one endpoint in each part.

An edge cutset separating two vertices is a set of edges whose removal leaves no path in a graph between those vertices. For a vertex set containing exactly one of the two vertices, its edge boundary is such a cutset.

A maximum cut has greatest size among all cuts of a finite graph.

Every finite graph with $m$ edges has a cut of a graph of size at least $m/2$, and hence a spanning bipartite graph with at least $m/2$ edges. Put each vertex independently on either side with equal probability. Every edge crosses with probability $1/2$, so linearity of expectation gives expected cut size $m/2$.

If a graph has even order $n$ and $m$ edges, it has a cut with equally sized parts and at leastcrossing edges. Choose one part uniformly among the $n/2$-vertex subsets. A fixed edge is separated with probabilityand apply linearity of expectation.

An unfriendly partition $V=A\bigsqcup B$ puts at least as many neighbours of every vertex in the opposite part as in its own part.

Every finite graph has an unfriendly partition. In a maximum cut, moving any vertex to the other side cannot increase the number of crossing edges, which is exactly the required neighbour inequality.

Take unfriendly partitions of an exhaustion by finite induced subgraphs and use a diagonal subsequence to stabilize the colour of each vertex. Local finiteness makes every neighbourhood stabilize after finitely many steps, so each unfriendly inequality passes to the limit.

Independently colour the vertices of a countable graph red or blue with equal probabilities. If every vertex has infinite degree, then each fixed vertex has infinitely many neighbours of each colour almost surely. A countable union of the exceptional null events is null, so such a colouring exists.