Essa é uma revisão anterior do documento!

Uma bipartição do conjunto de vértices de um grafo é dita uma unfriendly partition se cada vértice possui um número de vértices vizinhos da classe oposta a sua maior ou igual que o número de vértices vizinhos de sua própria classe.

Proposição: Todo grafo finito possui uma unfriendly partition.

Demonstração: De fato, basta tomar a partição que maximiza o número de arestas entre as classes. Desta forma, suponha que exista uma vértice que possui mais vizinhos de sua mesma classe que da classe oposta, trocando a classe do vértice obtemos uma partição com ainda mais arestas entre as classes. Contradição!

Proposição: Todo grafo enumerável localmente finito possui uma unfriendly partition.

Demonstração: Dado um grafo $G=(V,E)$ enumerável e localmente finito (i.e. $d(v)<\infty$ $\forall v \in V(G)$), podemos enumerar seus vértices como $V(G)=\{v_0,v_1,\ldots\}$