Учебник «Вероятность и статистика. 7–9 классы», часть 1, с. 85, §19
№124. Нарисуйте какой-либо граф, в котором 5 вершин со степенями 1, 2, 2, 3, 3.
Дано:
нужны 5 вершин со степенями 1, 2, 2, 3, 3
Найти:
граф с такими вершинами (или объяснить, что он невозможен)
Прежде чем рисовать, проверим, возможен ли такой граф. Найдём сумму степеней: . Это число нечётное, а по теореме о сумме степеней вершин в любом графе сумма степеней всех вершин чётная (она вдвое больше числа рёбер). Проще говоря, вершин нечётной степени здесь три (степени 1, 3 и 3), а в любом графе их число чётно (свойство из п. 19).
Значит, граф, у которого ровно пять вершин и степени этих вершин равны 1, 2, 2, 3, 3, нарисовать нельзя. (Это подтверждает и перебор: среди всех графов на пяти вершинах такого набора степеней нет.)
Но условие можно понять и по-другому: в графе есть пять вершин с такими степенями, а других вершин может быть сколько угодно. Тогда нужна ещё одна вершина нечётной степени — чтобы число вершин нечётной степени стало чётным. Возьмём шестую вершину степени 1 и соберём граф.
Построение. Нарисуем четырёхугольник АБДВ: у каждой его вершины степень 2. К вершине А добавим ребро АГ, а к вершине Б — ребро БЕ. Тогда степени вершин: А — 3 (АБ, АВ, АГ), Б — 3 (БА, БД, БЕ), В — 2, Д — 2, Г — 1, Е — 1.
Вершины Г, В, Д, А, Б имеют степени 1, 2, 2, 3, 3 — это как раз нужные пять вершин. Шестая вершина Е (синяя) лишняя: её степень 1 добавляет вершину нечётной степени, поэтому всего таких вершин четыре (Г, Е, А, Б), а сумма степеней чётна.
Замечание. Похожая задача №125 — про шесть вершин со степенями 1, 1, 2, 2, 3, 3: такой набор существует (сумма 12).
Ответ: Граф, у которого ровно пять вершин со степенями 1, 2, 2, 3, 3, не существует: сумма степеней нечётна, а должна быть чётной. Если в графе могут быть и другие вершины, то подходит граф на рисунке: у пяти его вершин степени 1, 2, 2, 3, 3, а шестая вершина имеет степень 1.
