Definição: 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! $\blacksquare$

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\}$ e, com isso, definir $V_n=\{v_0,\ldots,v_n\}$.

Assim, sendo $\mathcal{V}_n$ o conjunto de partições $(U_n,W_n)\subset V(G)\times V(G)$ tal que, para o conjunto $\{v\in V_n \mid N_G(v)\subseteq V_n\}$, $(U_n,W_n)$ seja sempre uma unfriendly partition.

Temos $\mathcal{V}_n\ne\varnothing$ pela proposição anterior.

Para todo $n\ge1$, todo $(U_n,W_n)\in\mathcal{V}_n$ (de $V_n$) induz uma partição $(U_{n-1},W_{n-1})\in\mathcal{V}_{n-1}$ (de $V_{n-1}$). Então, pelo Lema da Infinitude de König existe uma sequência infinita de partições onde cada $(U_n,W_n)\in\mathcal{V}_n$ é induzido pelo próximo elemento da sequência (um $(U_{n+1},W_{n+1})\in\mathcal{V}_{n+1}$).

Então $(\underset{n\in\mathbb{N}}{\bigcup}U_n,\underset{n\in\mathbb{N}}{\bigcup}W_n)$ é uma unfriendly partition de $G$. $\blacksquare$

Sabemos então que todo grafo finito e todo grafo enumerável localmente finito possui unfriendly partition.

Existe um contra-exemplo para grafo não enumerável, mas a resposta para um grafo enumerável qualquer ainda permanece em aberto.