An unfriendly partition 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.
Articles by others on the same topic
An **unfriendly partition** is a concept that arises in the context of graph theory and combinatorics. Generally, it refers to a way of partitioning a set of elements, such as vertices in a graph, where certain pairs of elements have a restricted relationship (e.g., they cannot be grouped together in the same subset) due to specific constraints.