(A version of [this question](https://mathoverflow.net/questions/235133/partitioning-finite-directed-graphs-into-3-incoming-sparse-sets) for undirected graphs.)


Let $G=(V,E)$ be a finite, simple, undirected graph. For $v\in V$ set 
$$
 N(v) := \{x\in V: \{x,v\}\in E\}.
$$ 
Is it possible to find a partition $P\_1,P\_2$ of $V$ such that for every $P\_i$ and $v\in P\_i$ we have $$|N(v)\cap P\_i| \leq |N(v)\cap(V\setminus P\_i)|$$?



Splitting the vertices of undirected graphs into 2 sparse sets
Yes, it is a variant of Lovasz partition lemma. Choose partition $V=P\_1\sqcup P\_2$ for which the number $E(G|\_{P\_1})+E(G|\_{P\_2})$of edges which join vertices of the same part is minimal possible. It works for each vertex $v$: else moving $v$ to other part decreases this value. 


