126 Может ли количество вершин нечётной

Пошаговое решение:

• Теорема о рукопожатиях: Сумма степеней всех вершин графа равна удвоенному числу ребер, то есть четному числу. \[\sum_{v \in V} deg(v) = 2|E|\]
• Пусть \(V\) - множество вершин графа, а \(E\) - множество ребер. Разделим множество вершин на два подмножества: \(V_{чет}\) - вершины с четной степенью и \(V_{нечет}\) - вершины с нечетной степенью.
• Сумму степеней всех вершин можно представить как: \[\sum_{v \in V} deg(v) = \sum_{v \in V_{чет}} deg(v) + \sum_{v \in V_{нечет}} deg(v)\]
• Так как \(\sum_{v \in V} deg(v)\) - четное число, а \(\sum_{v \in V_{чет}} deg(v)\) - тоже четное число (сумма четных чисел), то и \(\sum_{v \in V_{нечет}} deg(v)\) должно быть четным числом.
• Сумма нескольких нечетных чисел будет четной только в том случае, если количество этих чисел четно. Следовательно, количество вершин нечетной степени в графе должно быть четным.