Номер 126, страница 85, часть 1 - гдз по алгебре 7-9 класс учебник Высоцкий, Ященко

126 Может ли количество вершин нечётной степени в каком-нибудь графе равняться:

a) 0;

б) 1;

в) 2;

г) 3;

д) 4?

Для решения этой задачи воспользуемся леммой о рукопожатиях, которая является следствием теоремы о сумме степеней вершин графа. Теорема гласит, что в любом графе $G=(V, E)$ сумма степеней всех его вершин равна удвоенному числу рёбер:

$\sum_{v \in V} \deg(v) = 2|E|$

Из этой формулы следует, что сумма степеней всех вершин графа всегда является чётным числом, так как она равна $2|E|$.

Разобьём множество всех вершин $V$ на две группы: вершины с чётной степенью ($V_{четн}$) и вершины с нечётной степенью ($V_{нечетн}$). Тогда общую сумму степеней можно записать в виде:

$\sum_{v \in V} \deg(v) = \sum_{v \in V_{четн}} \deg(v) + \sum_{v \in V_{нечетн}} \deg(v)$

Рассмотрим слагаемые в правой части:

1. $\sum_{v \in V_{четн}} \deg(v)$ — это сумма чётных чисел, результат всегда будет чётным.
2. $\sum_{v \in V_{нечетн}} \deg(v)$ — это сумма нечётных чисел.

Зная, что общая сумма степеней чётна, и первое слагаемое (сумма чётных степеней) тоже чётно, мы можем заключить, что второе слагаемое (сумма нечётных степеней) также обязано быть чётным. Сумма нечётных чисел является чётной только в том случае, если количество слагаемых в ней чётно.

Таким образом, мы приходим к fundamental-ному выводу теории графов: количество вершин нечётной степени в любом графе всегда чётно.

Теперь проанализируем каждый из предложенных вариантов.

а) 0;
Число 0 является чётным. Следовательно, количество вершин нечётной степени может равняться нулю. Это означает, что в графе все вершины имеют чётную степень.
Пример: цикл $C_3$ (треугольник). В этом графе 3 вершины, и степень каждой из них равна 2 (чётное число). Количество вершин с нечётной степенью равно 0.
Ответ: Да, может.

б) 1;
Число 1 является нечётным. Согласно доказанному выше, количество вершин нечётной степени в любом графе должно быть чётным, поэтому оно не может равняться 1.
Ответ: Нет, не может.

в) 2;
Число 2 является чётным. Следовательно, в графе может быть 2 вершины нечётной степени.
Пример: граф, состоящий из двух вершин, соединённых одним ребром. Степень каждой из этих двух вершин равна 1 (нечётное число).
Ответ: Да, может.

г) 3;
Число 3 является нечётным. Количество вершин нечётной степени не может быть равно 3.
Ответ: Нет, не может.

д) 4?
Число 4 является чётным. Следовательно, в графе может быть 4 вершины нечётной степени.
Пример: полный граф на 4 вершинах ($K_4$). В этом графе каждая из 4 вершин соединена с тремя другими, поэтому степень каждой вершины равна 3 (нечётное число).
Ответ: Да, может.