Question

126 Может ли количество вершин нечётной степени в каком-нибудь графе равняться: а) 0; б) 1; в) 2; г) 3; д) 4? 127 На конференции собрались учёные. Могло ли оказаться так, что пятеро из них знакомы ровно с тремя другими, а все остальные имеют ровно четверых знакомых среди собравшихся?

Accepted Answer

126. Согласно лемме о рукопожатиях (теореме о сумме степеней вершин), сумма степеней всех вершин графа всегда чётна и равна удвоенному количеству рёбер. Из этого следует, что количество вершин с нечётной степенью в любом графе обязано быть чётным.
а) 0 — может (0 — чётное число);
б) 1 — не может (1 — нечётное число);
в) 2 — может (2 — чётное число);
г) 3 — не может (3 — нечётное число);
д) 4 — может (4 — чётное число).

127. Обозначим количество учёных как $n$.
Пусть 5 учёных имеют степень 3, а остальные $(n - 5)$ учёных имеют степень 4.
Сумма степеней вершин: $S = 5 \cdot 3 + (n - 5) \cdot 4 = 15 + 4n - 20 = 4n - 5$.
Число $4n$ всегда чётное, а $4n - 5$ всегда нечётное. По теореме о сумме степеней вершин, эта сумма должна быть чётной.
Ответ: Нет, не могло.

Ответ ассистента

Другие решения