126 Может ли количество вершин нечётной степени в каком-нибудь графе няться: a) 0; б) 1; в) 2; г) 3; д) 4?

По теореме о сумме степеней, сумма степеней всех вершин графа равна удвоенному числу ребер, следовательно, эта сумма должна быть четной. Вершины нечетной степени вносят нечетный вклад в эту сумму. Чтобы сумма была четной, число вершин нечетной степени должно быть четным.

a) 0 - четное число. Может.

б) 1 - нечетное число. Не может.

в) 2 - четное число. Может.

г) 3 - нечетное число. Не может.

д) 4 - четное число. Может.

Ответ: Количество вершин нечетной степени может равняться 0, 2 или 4.