Задача 87972

Темы:    [ Четность и нечетность ] [ Степень вершины ]

Сложность: 3- Классы: 6,7,8

Условие

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

Решение

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

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

Замечания

См. также задачу 98656.

Источники и прецеденты использования

неизвестно