Para tratar de ser precisos, definimos el número de amistades separadas (para una distribución en dos grupos) como el número total de parejas (no ordenadas) de amigos que quedaron en distintos grupos. En términos de la gráfica asociada a la relación de amistad, el número de amistadas separadas es el número de aristas que van de un conjunto de vértices al otro.
Entonces, cada separación en dos grupos tiene asociado un número (el número de amistadas separadas). Este número no puede ser superior al total de amistades existentes, por lo tanto, debe existir una forma de separar con el mayor número posible de amistades separadas (aquí es donde entra el principio extremal). A este tipo de separación la llamaremos separación máximal. Notemos que no hemos dicho que la separación es única.
Por último, demostremos que una separación maximal satisface lo deseado. Supongamos que, en una separación maximal, hay una persona con más amigos en su grupo que en el otro. Entonces, si cambiamos a esa persona de grupo, se aumentará el número de amistadas separadas en la separación maximal elegida. Pero eso contradice la hipótesis de separación maximal.
En términos más matemáticos se puede explicar como sigue: Supongamos que para una separación maximal, existe un persona P con x + y amigos, de los cuales x están en el mismo grupo, y además x > y. Entonces, al cambiar de grupo a P, se eliminan “y” parejas del total de número de amistadas separadas, pero se agregan “x”, por ende, el número de parejas separadas crece en x-y, y de ahí la contradicción a la maximalidad de la separación.
La solución anterior también nos da un algoritmo para encontrar la separación. El algoritmo consiste en acomodar a la gente como sea y, de existir alguien que no satisfaga la condición (de tener al menos la mitad de sus amigos en el otro grupo), entonces a ese alguien lo cambiamos de grupo. Se continua el proceso hasta llegar el momento en que todas las personas satisfacen la condición. La razón por la que el proceso termina es que, en cada una de las movidas, se está aumentando el número de amistades separadas. Y ese número no puede crecer al infinito, pues se trata de un número finito de amistades existentes.
