Infinite non-splittable graphs

Question

Let $G=(V,E)$ be a graph. For $v\in V$ we set $N(v)=\{w\in V:\{v,w\}\in E\}$. We say that $G$ is splittable if there are $S,T\subseteq V$ with $S\cap T=\emptyset$ and $S\cup T = V$ such that

1. for all $s\in S$ we have $|N(s)\cap S| \leq |N(s) \cap T|$, and symmetrically
2. for all $t\in T$ we have $|N(t)\cap T| \leq |N(t) \cap S|$.

Is there a non-splittable infinite graph? How about a non-splittable countable graph?

Answer 1

These partitions are normally called unfriendly. Every finite graph has an unfriendly partition (choose a partition that has the maximum possible number of cross edges). It was conjectured by Cowan and Emerson that every graph should have an unfriendly partition, but Milner and Shelah found an uncountable counterexample. The conjecture is still open for countable graphs. See the conjecture's page on the Open Problem Garden for references and more details.