Докажите, что число нечетных узлов графа всегда четно.

Поставьте в каждой вершине графа
число, равное количеству выходящих
из него путей. Если мы сложим
все эти числа, то получим четное
число, так как каждый путь, соединяющий
две вершины, считается
дважды. Отсюда следует, что число
нечетных вершин всегда четно