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

Для решения этой задачи нам понадобится теорема о рукопожатиях (лемма о сумме степеней). Она утверждает, что сумма степеней всех вершин графа равна удвоенному количеству ребер (то есть является четным числом). Разберем каждый вариант: а) **0**: Да, может. Например, граф без ребер имеет 0 вершин нечетной степени. б) **1**: Нет, не может. Если есть одна вершина с нечетной степенью, то сумма степеней всех вершин будет нечетной, что противоречит теореме о рукопожатиях. Значит такое невозможно. в) **2**: Да, может. Самый простой пример: граф с одним ребром. У него две вершины степени 1. г) **3**: Нет, не может. Если есть три вершины с нечетной степенью, то сумма степеней всех вершин будет нечетной. Это противоречит теореме о рукопожатиях, значит такое невозможно. д) **4**: Да, может. Например, возьмем граф в виде прямоугольника. Все 4 вершины будут степени 2 и возьмем еще один отрезок (еще одно ребро) по диагонали. У нас получился граф с 4 вершинами степени 3, то есть 4 вершины нечетной степени. **Ответ:** Количество вершин нечетной степени в графе может равняться **0, 2, или 4**; не может равняться 1 или 3.