От Докажите, что число субъектов России с нечётным числом соседей чётно.

Аналогичная задача про графы ниже (пункт б)

Докажите, что в любом графе

 а) сумма степеней всех вершин равна удвоенному числу рёбер (и следовательно, чётна);

 б) число вершин нечётной степени чётно.

Решение

 а) При сложении степеней вершин каждое ребро учитывается дважды: по разу для каждой из вершин, которые оно соединяет.

 б) Сразу следует из а) и того очевидного факта, что сумма нечётного числа нечётных чисел нечётна.