Может ли количество вершин нечётной степени в каком-нибудь графе равняться: а) 0; б) 1; в) 2; г) 3; д) 47?

Для решения задач на графы воспользуемся «Леммой о рукопожатиях»: сумма степеней всех вершин графа всегда чётна и равна удвоенному количеству рёбер ($2E = \sum deg(v)$). Из этого следует, что количество вершин с нечётной степенью всегда должно быть чётным. **126. Может ли количество вершин нечётной степени в каком-нибудь графе равняться:** а) 0 — Да (например, в пустом графе или цикле); б) 1 — Нет (количество нечётных вершин должно быть чётно); в) 2 — Да; г) 3 — Нет (нечётно); д) 47 — Нет (нечётно). **Ответ: а), в).** **127. Могло ли оказаться так, что пятеро из них знакомы ровно с тремя другими, а все остальные имеют ровно четверых знакомых?** Если мы представим людей как вершины, а знакомства как рёбра, то у нас было бы 5 вершин степени 3 (нечётная степень). По лемме о рукопожатиях количество нечётных вершин должно быть чётным. Число 5 — нечётное. **Ответ: Нет.** **129. Докажите, что сумма степеней всех вершин графа вдвое больше числа рёбер.** Каждое ребро соединяет две вершины. При подсчёте суммы степеней каждое ребро учитывается дважды: один раз для одной вершины, которую оно соединяет, и второй раз — для другой. Таким образом, сумма степеней всех вершин равна $2 imes$ (количество рёбер). **130. В некотором графе 6 вершин, степени которых равны: Сколько всего рёбер в этом графе?** Используем формулу $E = ?rac{\sum deg(v)}{2}$: а) $E = ?rac{2 + 2 + 3 + 3 + 4 + 4}{2} = ?rac{18}{2} = 9$. б) $E = ?rac{0 + 1 + 2 + 2 + 3 + 4}{2} = ?rac{12}{2} = 6$. **Ответ: а) 9 рёбер; б) 6 рёбер.**