Какой может быть сумма степеней вершин графа? Выберите все верные варианты ответа. 406 111 76 13 199

Привет! Давай разберёмся с этим заданием по теории графов.

Суть в чём:

Теорема о рукопожатиях гласит, что сумма степеней всех вершин в любом графе всегда равна удвоенному количеству его рёбер. А так как количество рёбер — это целое число, то и удвоенное количество рёбер тоже всегда будет чётным числом.

Что это значит для нас?

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

Теперь посмотрим на варианты ответов:

• 406 — чётное число. Может быть.
• 111 — нечётное число. Не может быть.
• 76 — чётное число. Может быть.
• 13 — нечётное число. Не может быть.
• 199 — нечётное число. Не может быть.

Вывод:

Верные варианты — это те, где сумма степеней является чётным числом.

Ответ: 406, 76