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?



Infinite non-splittable graphs
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](http://www.openproblemgarden.org/op/unfriendly_partitions) for references and more details.


