Every rayless graph has an unfriendly partition (Q5894428): Difference between revisions

A bipartition of the vertex set of a graph is called unfriendly if every vertex has at least as many neighbors in the other class as in its own. Every finite graph has an unfriendly partition but there exist infinite graphs that admit no unfriendly partition. The unfriendly partition conjecture says that every countable graph has an unfriendly partition of its vertex set. In this paper it is proved that every rayless graph (countable or not) admits an unfriendly partition. The proof uses transfinite induction.