Задача 027 — Задачи на Графы

В кружке занимаются $2 n$ человек. Кружок называется однородным, если у каждого кружковца одно и то же количество друзей в кружке. Докажите, что кружок однороден тогда и только тогда, когда при любом его разбиении на две команды по $n$ учеников количества пар друзей в командах равны.

Подсказка

Разделите вершины на две равные группы $A$ и $B$ .

Решение

Рассмотрим граф знакомств. Разделим вершины на две равные группы $A$ и $B$ . Пусть $S_{A}\left(S_{B}\right)$ — сумма степеней вершин, входящих в $A(B)$ , а $R$ — количество знакомств между учениками из $A$ и $B$ . Тогда количество знакомств $N_{A}$ внутри $A$ равно $\left(S_{A}-R\right) / 2$ . 1) Пусть у всех одинаковое число друзей. Тогда при разбиении на равные группы $A$ и $B, S_{A}=S_{B}$ , следовательно, $N_{A}=N_{B}$ . 2) Пусть не у всех одинаковое число друзей. Составим $A$ из $n$ вершин с наименьшими степенями. Тогда $S_{A}<S_{B}$ , и, следовательно, $N_{A}<N_{B}$ .