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

Задание 126

Это задание связано с теоремой о рукопожатиях (или леммой о степенях вершин). Она гласит, что сумма степеней всех вершин графа всегда равна удвоенному числу его рёбер. Из этого следует, что сумма степеней всех вершин — всегда чётное число. А ещё это значит, что количество вершин с нечётной степенью в любом графе всегда является чётным числом.

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

а) 0

Может ли количество вершин нечётной степени быть равно 0? Да, может. Это будет граф, где все вершины имеют чётную степень. Например, простой цикл из 3 вершин (треугольник), где у каждой вершины степень 2. Или граф, где вообще нет вершин (пустой граф).

Ответ: да.

б) 1

Может ли количество вершин нечётной степени быть равно 1? Нет, не может. Согласно теореме, количество вершин с нечётной степенью всегда чётное. 1 — нечётное число.

Ответ: нет.

в) 2

Может ли количество вершин нечётной степени быть равно 2? Да, может. Например, простой граф, состоящий из двух вершин, соединённых одним ребром. У каждой из этих вершин степень 1, что является нечётной степенью. Всего 2 вершины с нечётной степенью.

Ответ: да.

г) 3

Может ли количество вершин нечётной степени быть равно 3? Нет, не может. Как мы уже выяснили, количество вершин с нечётной степенью всегда чётное. 3 — нечётное число.

Ответ: нет.

п) 4

Может ли количество вершин нечётной степени быть равно 4? Да, может. Например, можно построить граф, где 4 вершины имеют степень 1, а остальные вершины — чётную степень. Или, например, граф "звезда" с 5 вершинами: центральная вершина соединена со всеми остальными четырьмя. Центральная вершина будет иметь степень 4 (чётная), а 4 крайние вершины — степень 1 (нечётная). Всего 4 вершины с нечётной степенью.

Ответ: да.