Регулярные графы

Это продолжение темы о графах, начало смотрите здесь.

Определение. Граф, степени всех вершин которого одинаковы, называется регулярным.

Задача 1. В некоторой компании любые два знакомых не имеют общих знакомых, а любые два незнакомых имеют ровно двух общих знакомых. Докажите, что в этой компании все имеют одинаковое число знакомых.

Показать решение

Задача 2. В лагере отдыхают

    \[50\]

школьников. Известно, что среди любых школьников найдется по крайней мере один, знакомый с тремя остальными. Докажите, что найдется школьник, знакомый со всеми остальными школьниками.

Показать решение

Задача 3. На конгресс собрались ученые, среди которых есть знакомые друг с другом. Оказалось, что никакие двое ученых, имеющих равное число знакомых, не имеют общих знакомых. Докажите, что найдется ученый, имеющий ровно одного знакомого.

Показать решение

Задача 4. В трехмерном пространстве выбраны

    \[8\]

точек так, что никакие три из них не лежат на одной прямой. Проведено

    \[17\]

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

Показать решение

Источник: О.И. Мельников “Теория графов в занимательных задачах”, М.: Книжный дом “ЛИБРОКОМ”, 2011.

Оставьте свой отзыв

Добавить изображение