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

3 Может ли в эйлеровом графе не быть вершин нечётной степени? Может ли быть только одна вершина нечётной степени; две вершины нечётной степени; три или больше?

Для ответа на этот вопрос воспользуемся определениями и теоремами из теории графов.

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

Ключевая теорема (критерий эйлеровости): связный граф является эйлеровым тогда и только тогда, когда степени всех его вершин чётны.

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

Может ли в эйлеровом графе не быть вершин нечётной степени?

Да, может. Более того, это является обязательным условием для эйлерова графа. Согласно критерию эйлеровости, чтобы в связном графе существовал эйлеров цикл, необходимо и достаточно, чтобы все его вершины имели чётную степень. Отсутствие вершин нечётной степени как раз и означает, что все вершины имеют чётную степень.

Ответ: Да, может.

Может ли быть только одна вершина нечётной степени?

Нет, не может. Это невозможно ни в каком графе, не только в эйлеровом. Согласно лемме о рукопожатиях, сумма степеней всех вершин графа всегда является чётным числом ($2|E|$). Если бы в графе была только одна вершина нечётной степени, а остальные имели бы чётные степени, то общая сумма степеней была бы нечётной (сумма чётных чисел — чётное число, плюс одно нечётное — даёт нечётное число). Это противоречит лемме о рукопожатиях. Следовательно, число вершин нечётной степени в любом графе должно быть чётным.

Ответ: Нет, не может.

Может ли быть две вершины нечётной степени?

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

Стоит отметить, что связный граф, в котором есть ровно две вершины нечётной степени, называется полуэйлеровым. В таком графе существует эйлеров путь (путь, проходящий через каждое ребро ровно один раз), но не существует эйлерова цикла. Такой путь начинается в одной из вершин нечётной степени и заканчивается в другой. Однако, поскольку в вопросе речь идет именно об эйлеровом графе (с циклом), ответ отрицательный.

Ответ: Нет, не может.

Может ли быть три или больше?

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

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

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

Ответ: Нет, не может.