Это продолжение темы о графах, начало смотрите здесь.
Определение. Граф, степени всех вершин которого одинаковы, называется регулярным.
Задача 1. В некоторой компании любые два знакомых не имеют общих знакомых, а любые два незнакомых имеют ровно двух общих знакомых. Докажите, что в этой компании все имеют одинаковое число знакомых.
Показать решение
Построим граф знакомств
, в котором вершины изображают людей, и две вершины смежны тогда и только тогда, когда соответствующие люди знакомы. Рассмотрим две смежные вершины графа
и
. Пусть вершине
смежны вершины
. Эти вершины не смежны с вершиной
по условию. Несмежные вершины
и
имеют общую вершину
, значит, у них есть еще одна общая вершина, пусть это вершина
. Вершина
не смежна вершине
.

Аналогично для каждой вершины
найдется вершина
, смежная с вершинами
и
и несмежная с вершиной
. Кроме того, вершины
попарно различны, так как если
, то люди, соответствующие вершинам
и
, будут иметь более двух общих знакомых.

Поэтому степень вершины
больше либо равна степени вершины
. Точно так же доказывается, что степень вершины
больше либо равна степени вершины
. Следовательно, степени вершин
и
равны.
Степени двух смежных вершин одинаковы. Однако для двух несмежных вершин
и
существует третья вершина
, смежная с
и
. Значит, будут одинаковы и степени всех несмежных вершин. Тем самым в компании все имеют одинаковое число знакомых.
Задача 2. В лагере отдыхают
школьников. Известно, что среди любых школьников найдется по крайней мере один, знакомый с тремя остальными. Докажите, что найдется школьник, знакомый со всеми остальными школьниками. Читать полностью ‘Регулярные графы’ »