Номер 127, страница 85, часть 1 - гдз по алгебре 7-9 класс учебник Высоцкий, Ященко

127 На конференцию собрались учёные. Могло ли оказаться так, что пятеро из них знакомы ровно с тремя другими, а все остальные имеют ровно четверых знакомых среди собравшихся?

Для ответа на этот вопрос можно использовать базовые принципы теории графов. Представим всех ученых на конференции в виде вершин графа, а знакомства между ними — в виде ребер. Если два ученых знакомы, их вершины соединены ребром. Количество знакомых у одного ученого соответствует степени его вершины в графе (количеству ребер, которые из нее исходят).

Согласно условию задачи, в этом графе есть:

• 5 вершин, имеющих степень 3 (пятеро ученых знакомы ровно с тремя другими).
• Все остальные $N-5$ вершин имеют степень 4 (где $N$ — общее число ученых).

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

Следствием из этой леммы является тот факт, что количество вершин с нечетной степенью в любом графе должно быть четным (0, 2, 4, 6 и т.д.).

Проанализируем наш случай с этой точки зрения:

В описанной ситуации есть ровно 5 ученых, у которых по 3 знакомых. Число 3 — нечетное. Следовательно, в нашем графе есть 5 вершин с нечетной степенью.

У всех остальных ученых по 4 знакомых. Число 4 — четное. Так что остальные вершины имеют четную степень.

Таким образом, общее количество вершин с нечетной степенью в этом гипотетическом графе равно 5.

Число 5 — нечетное. Это напрямую противоречит следствию из леммы о рукопожатиях, которое требует, чтобы количество вершин с нечетной степенью было четным.

Следовательно, такая конфигурация знакомств невозможна.

Ответ: Нет, так оказаться не могло.