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

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

а) Да, может. Например, граф без ребер и вершин. Все вершины имеют четную степень 0.

б) Нет, не может. Если одна вершина имеет нечетную степень, то сумма всех степеней будет нечетной.

в) Да, может. Например, две вершины со степенью 1.

г) Нет, не может. Если три вершины имеют нечетную степень, то сумма всех степеней будет нечетной.

д) Да, может. Например, четыре вершины со степенью 1.

Ответ: a) да; б) нет; в) да; г) нет; д) да.