Доказать что кол-во вершин любого графа в нечетной степени всегда четно (не малое вознагрождение) нужно в течении 20 минут

Доказательство. Пусть a1, a2, a3, ..., ak - это степени четных вершин графа, а b1, b2, b3, ..., bm - степени нечетных вершин графа. Сумма a1+a2+a3+ ...+ak+b1+b2+b3+ ...+bm ровно в два раза превышает число ребер графа. Сумма a1+a2+a3+ ...+ak четная (как сумма четных чисел), тогда сумма b1+b2+b3+ ...+bm должна быть четной. Это возможно лишь в том случае, если m - четное, то есть четным является и число нечетных вершин графа. Что и требовалось доказать.

Можно так:

Пусть есть пустой граф с n вершинами (вершина степени 0 считается чётной степени).

1) Если мы добавим 1 ребро, то получим 2 вершины нечётной степени. Если добавить ещё 1 ребро, которое соединяет какие-либо другие вершины, то получим ещё 2 вершины нечётной степени. Всего вершин 4 и т. д.

2) Если добавить ребро соединяющее вершину чётной степени и нечётной, то вершина которая была нечётной степени станет чётной, а вершина чётной степени перейдёт в нечётную. При этом количество вершин нечётной степени не изменится.

3) соединяются 2 вершины нечётной степени: тогда обе вершины станут чётной степени, а количество вершин нечётной степени уменьшится на 2.