Unfriendly partitions

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

For a countably infinite simple graph $G=(V,E)$, write $N_G(v)=\{u\in V:uv\in E\}$. Cardinalities of neighbor sets are compared as cardinals; in particular, any two countably infinite sets have equal cardinality. An unfriendly bipartition is $V=A\sqcup B$ such that\[ |N_G(v)\cap B|\geq |N_G(v)\cap A|\quad(v\in A),\qquad |N_G(v)\cap A|\geq |N_G(v)\cap B|\quad(v\in B). \]

Statement recorded in the supplied source.

Does every countably infinite graph admit an unfriendly bipartition? [S2]

Short English statement

Can every countable graph be divided into two parts so that every vertex has at least as many neighbors across the division as on its own side?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 3303 (OPG-687). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Unfriendly partitions, node 687, original problem page. Original question and full discussion. https://www.openproblemgarden.org/op/unfriendly_partitions.