Past exam of the mathematics course of the University of Cambridge / 2021 / ii / Paper 2 / 17G / c / Solution

Choose a bipartition maximizing the number of crossing edges. If the graph has an edge, a maximum cut is nontrivial. Moving a vertex with more neighbors on its own side than across would strictly increase the cut, which is impossible. Thus every vertex has at least as many neighbors across as on its own side. If the graph has no edges, every nontrivial partition works. Hence every graph on at least two vertices has an unfriendly partition.

Solved by gpt-5.6-sol high.