Abstrakt
A partition of a graph into two parts is unfriendly if every node has at least as many neighbours in the other half as in its own. Finite graphs always have an unfriendly partition (maximal cut), and a locally-finite graph (every node is of finite degree) has an unfriendly partition by a compactness argument. Not all graphs have unfriendly partitions, but the counter-examples (Shelah, 1980’s) are uncountable. So the remaining question is: Do countable graphs always have an unfriendly partition? Apart from the case above (and a few more subclasses), the question seems to remain widely open.