B10. a) На конференцию собрались учёные. Могло ли оказаться так, что каждый из них знаком с четырьмя другими учёными, кроме троих, которые знакомы ровно с пятью другими? б) В поход собралась большая группа туристов. Некоторые из них были знакомы прежде. Покажите, что туристов, которые бы- ли знакомы с нечётным количеством других туристов, чётное число.

• a) Нет, такого быть не могло.

Если каждый из учёных знаком с четырьмя другими, то общее число знакомств должно быть чётным (так как каждое знакомство учитывается дважды). Если есть трое, знакомых с пятью другими, то они добавляют нечётное число знакомств (3 * 5 = 15), что нарушает общее правило.

• б) Доказательство:

Предположим, что у нас есть группа туристов. Рассмотрим каждого туриста и количество его знакомых. Если сложить все количества знакомых, то получится чётное число, так как каждое знакомство учитывается дважды. Пусть K - количество туристов, знакомых с нечётным числом других туристов. Сумма степеней всех этих туристов (знакомых с нечётным числом других) должна быть чётной, так как сумма всех степеней графа чётна. Если бы K было нечётным, то сумма нечётных чисел была бы нечётной, что противоречит тому, что она должна быть чётной. Следовательно, K должно быть чётным.