Задача
COM-B1-M11-P005 Степени
#5
★☆☆☆☆ Уровень 1 из 5
В графе степени вершин равны \(1,2,2,3,4\). Существует ли такой граф?
Проверьте сумму степеней.
Сумма степеней равна \(12\), четность не запрещает. Построим явно. Назовем вершины \(A,B,C,D,E\). Соединим \(A\) со всеми остальными: у \(A\) степень \(4\), а у остальных пока степень \(1\). Теперь добавим ребра \(BC\) и \(BD\). Тогда степени равны: \(\deg A=4\), \(\deg B=3\), \(\deg C=2\), \(\deg D=2\), \(\deg E=1\). Значит такой граф существует.
Важно: четная сумма степеней необходима, но не всегда достаточна; здесь нужно построение.