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

Question

Вопрос:

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

Фотография

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

Accepted Answer

126. В любом графе количество вершин нечётной степени всегда должно быть чётным (согласно лемме о рукопожатиях, сумма степеней всех вершин равна удвоенному количеству рёбер, то есть чётна). Из этого следует: а) **Да**, 0 — чётное число. б) **Нет**, 1 — нечётное число. в) **Да**, 2 — чётное число. г) **Нет**, 3 — нечётное число. д) **Да**, 4 — чётное число. 127. Представим учёных как вершины графа, а знакомства — как рёбра. По условию 5 вершин имеют степень 3. Сумма степеней этих пяти вершин равна $5 \cdot 3 = 15$. Степени всех остальных вершин равны 4 (чётное число). Сумма любого количества чётных чисел всегда чётна. Тогда общая сумма степеней всех вершин будет: $15 + (\text{чётное число}) = \text{нечётное число}$. Согласно теории графов, сумма степеней всех вершин всегда должна быть чётной (равна $2E$). Полученное противоречие означает, что такая ситуация невозможна. **Ответ: нет, не могло.**

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

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