Задание 9. Сколько может быть вершин графа с нечетной валентностью?

Теорема гласит: Количество вершин с нечётной степенью всегда чётно.

Доказательство: Сумма степеней всех вершин графа равна удвоенному числу рёбер (то есть чётному числу). Если бы число нечётных вершин было нечётным, то и сумма их степеней была бы нечётной. Сумма же степеней чётных вершин всегда чётна. Но сумма чётного и нечётного чисел не может быть чётной, что противоречит утверждению о чётности суммы степеней всех вершин графа.