Предположим противное. Рассмотрим граф $G$, в котором люди являются вершинами, а два человека соединены ребром, если они знакомы. Тогда граф $k$-разбиваем, если его вершины можно правильно окрасить в $k$ цветов (т. е. окрасить так, чтобы соединённые вершины имели разные цвета). Мы будем пользоваться следующей известной леммой.

Лемма. Пусть в графе нет циклов нечётной длины. Тогда его вершины можно правильно раскрасить двумя красками.

Доказательство. Ясно, что достаточно доказать лемму для связного графа. Расстоянием между двумя вершинами $X$ и $Y$ назовём наименьшую длину пути, соединяющего эти вершины.

Зафиксируем некоторую вершину $A$, и покрасим все вершины, находящиеся на нечётном расстоянии от $A$, в красный цвет, а остальные вершины — в синий цвет. Докажем, что указанная раскраска — искомая. Предположим противное — имеется ребро, соединяющее, скажем, красные вершины $B$ и $C$. Рассмотрим кратчайшие пути $A = B_0, B_1, \dots, B_{2n-1} = B$ и $A = C_0, C_1, \dots, C_{2m-1} = C$, ведущие из $A$ в $B$ и в $C$. Взяв наибольший индекс $i$ такой, что $B_i = C_i$, получим цикл нечётной длины $B_{i+1}, \dots, B_{2n-1}, C_{2m-1}, C_{2m-2}, \dots, C_i = B_i$. Противоречие. $\Box$

По лемме, в нашем графе $G$ есть нечётный цикл — иначе его вершины можно окрасить даже в два цвета. Выберем в $G$ нечётный цикл $C$ минимальной длины $n$. Тогда не существует рёбер, соединяющих вершины этого цикла, кроме рёбер самого цикла. Действительно, любое такое ребро разбивает цикл на два меньших по длине, причём один из них нечётен. Значит, в этом случае нашёлся бы нечётный цикл меньшей длины.

Далее, покажем, что любая вершина $x$, не принадлежащая $C$, соединена не более, чем с двумя вершинами $C$. Если $C$ содержит три вершины, то утверждение верно, иначе $x$ вместе с вершинами $C$ образует компанию из 4 попарно знакомых человек.

Пусть теперь в $C$ больше трёх вершин. Предположим, что $x$ соединена с вершинами $v_1, v_2, v_3$ этого цикла. Участок цикла между какими-то двумя из них (скажем, между $v_1$ и $v_2$) содержит нечётное количество рёбер $d$. Если $d < n-2$, то этот участок вместе с вершиной $x$ образует нечётный цикл длины $d+2 < n$, что невозможно. Значит, $d \ge n-2$ ребра, а это значит, что вершины $v_1, v_3, v_2$ идут в цикле подряд. Но тогда найдётся цикл $v_1, v_3, x$ длины 3, что невозможно.

Теперь мы можем предъявить требуемое разбиение: поместим в одну группу вершины цикла $C$, а в другую (назовём её $D$) — все остальные. Вершины цикла $C$, очевидно, нельзя правильно окрасить в два цвета. Осталось показать, что между вершинами группы $D$ есть ребро (тогда она 1-неразбиваема). Предполагая противное, покажем, что $G$ можно окрасить в три цвета. Сначала окрасим все вершины $C$, кроме одной, попеременно в цвета 1 и 2, а оставшуюся окрасим в цвет 3; поскольку между этими вершинами нет других рёбер, раскраска этого цикла — правильная. Окрасить теперь вершины группы $D$ по очереди. Каждая очередная вершина соединена не более, чем с двумя вершинами из $C$, и не соединена с вершинами из $D$; значит, можно выбрать для неё цвет, отличный от цветов её соседей. Итого, граф $G$ можно правильно окрасить в три цвета, что противоречит условию.