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

Решение:

По теореме о сумме степеней вершин графа, сумма степеней всех вершин графа равна удвоенному числу его рёбер. Это означает, что сумма степеней всех вершин всегда является чётным числом. Если бы количество вершин нечётной степени было нечётным, то сумма степеней нечётных вершин была бы нечётной, а сумма степеней чётных вершин — чётной. В итоге, сумма всех степеней оказалась бы нечётной, что противоречит теореме.

Следовательно, количество вершин нечётной степени в любом графе всегда чётно.

• а) 0 — чётно. Возможно.
• б) 1 — нечётно. Невозможно.
• в) 2 — чётно. Возможно.
• г) 3 — нечётно. Невозможно.
• д) 4 — чётно. Возможно.

Ответ: Не может равняться 1 и 3.