Учебник «Вероятность и статистика. 7–9 классы», часть 1, с. 85, §19
№127. На конференцию собрались учёные. Могло ли оказаться так, что пятеро из них знакомы ровно с тремя другими, а все остальные имеют ровно четверых знакомых среди собравшихся?
Дано:
пятеро учёных знакомы ровно с 3 другими; все остальные — ровно с 4
Найти:
могло ли так быть
Составим граф знакомств: каждого учёного изобразим вершиной, а двух знакомых между собой учёных соединим ребром. Тогда степень вершины — это число знакомых у этого учёного.
По условию у пятерых учёных по 3 знакомых — пять вершин степени 3, то есть нечётной. У всех остальных по 4 знакомых — вершины степени 4, чётной. Значит, в графе ровно пять вершин нечётной степени.
Но в любом графе количество вершин нечётной степени чётно (свойство из п. 19), а число 5 нечётно. Значит, такого графа знакомств быть не может.
Проверим другим способом — по сумме степеней. Пусть всего собралось учёных (). Сумма степеней всех вершин равна . Это число нечётное при любом , а сумма степеней вершин любого графа чётна (она вдвое больше числа рёбер, то есть числа пар знакомых). Противоречие.
Иначе говоря, «рукопожатия» происходят парами: если сложить числа знакомств всех участников, каждая пара знакомых посчитана дважды, поэтому сумма чётная. Ответ: нет, не могло.
Ответ: Нет. Количество вершин нечётной степени в графе знакомств чётное, а здесь их было бы пять.
