Задание 4. Может ли количество вершин нечетной степени в каком-нибудь графе равняться: 1) 3 2) 5 3) 6 4) 8 5) 1

Ответ: 3) 6

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

Проверим предложенные варианты:

• 1) 3 - нечетное число
• 2) 5 - нечетное число
• 3) 6 - четное число
• 4) 8 - четное число
• 5) 1 - нечетное число

Из предложенных вариантов только 6 и 8 являются четными числами. Однако, поскольку спрашивается, может ли равняться, то достаточно одного подходящего варианта.

Ответ: 3) 6