ЗАДАНИЕ 5 Выберите подходящий вариант в выпадающем списке Может ли количество вершин нечётной степени в каком-нибудь графе равняться: a) 0 б) 3 в) 1000 г) 1001

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

Лемма о рукопожатиях утверждает, что в любом графе сумма степеней всех вершин равна удвоенному числу рёбер. Формально это записывается так: $$\sum_{v \in V} deg(v) = 2|E|$$

где: $$V$$ - множество вершин графа, $$E$$ - множество рёбер графа, $$deg(v)$$ - степень вершины $$v$$.

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

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

Среди предложенных вариантов только 0 является чётным числом.

Ответ: a) 0