Условие
В простом неориентированном графе шесть вершин имеют степени 3,3,2,2,2,2. Сколько рёбер? Постройте граф с такими степенями.
Решение по шагам
Каждое ребро добавляет единицу степени двум концам. Поэтому сумма степеней равна удвоенному числу рёбер: 3+3+2+2+2+2=14, откуда |E|=7.
Построение: возьмите цикл из шести вершин 0−1−2−3−4−5−0. Все степени пока равны 2. Добавьте диагональ 0−3: степени её концов станут 3, остальные останутся 2. Получен простой граф с нужным набором.
Проверка результата
У цикла шесть рёбер, новая диагональ — седьмое. Прямой подсчёт концов рёбер даёт степени 3,2,2,3,2,2.
Типичная ошибка
Чётная сумма степеней — необходимое условие, но не достаточное для существования простого графа с произвольной последовательностью степеней. Здесь существование доказывает явная конструкция.
Что даёт этот метод
Из той же леммы следует, что число вершин нечётной степени всегда чётно: их нечётные вклады должны иметь чётную сумму.
Дальше по теме
Комбинаторика и дискретная математика: другие задачи и разборы.
Учебное условие и объяснение сформулированы редакцией damirock.com. Это самостоятельный разбор, а не официальный билет или ключ экзамена. Числа относятся к модели задачи.