Учебник «Вероятность и статистика. 7–9 классы», часть 1, с. 85, §19
№126. Может ли количество вершин нечётной степени в каком-нибудь графе равняться:
а) 0; б) 1; в) 2; г) 3; д) 4?
Дано:
граф с вершинами нечётной степени; , , , ,
Найти:
для каких такой граф существует
Вспомним свойство из п. 19: в любом графе количество вершин нечётной степени чётно. Поэтому числа 1 и 3 (нечётные) получиться не могут, а 0, 2 и 4 (чётные) — могут. Проверим и то и другое.
Почему это свойство верно. Пусть в графе вершин нечётной степени, а остальные вершины имеют чётную степень. Сумма степеней всех вершин чётна (теорема о сумме степеней: она вдвое больше числа рёбер). Сумма степеней вершин чётной степени чётна, значит, чётна и сумма степеней вершин нечётной степени. Но сумма нечётных чисел чётна только тогда, когда слагаемых чётное число. Значит, чётно.
а) Может. В треугольнике степени всех вершин равны 2 — вершин нечётной степени нет (рисунок а). Подойдёт и граф из одной вершины без рёбер.
б) Не может: 1 — число нечётное, а вершин нечётной степени в любом графе чётное количество.
в) Может. В цепи из трёх вершин степени равны 1, 2, 1: нечётных вершин две (рисунок в).
г) Не может: 3 — нечётное число.
д) Может. В «звезде» из четырёх вершин центральная вершина имеет степень 3, а три других — степень 1: вершин нечётной степени четыре (рисунок д).
Замечание. Мы дополнительно проверили это перебором: во всех графах на 1–6 вершинах количество вершин нечётной степени принимает только значения 0, 2, 4 и 6.
Ответ: а), в), д) Да; б), г) нет.
