124 Существует ли граф, в котором 5 вершин, и они имеют степени 1, 2, 2, 3, 3? Изобразите такой граф или объясните, почему это невозможно. 125 Придумайте и нарисуйте два неодинаковых графа, в каждом из которых 6 вершин со степенями 1, 1, 2, 2, 3, 3.

**Ответ: Да, такой граф существует.** Для проверки возможности существования графа с заданными степенями вершин воспользуемся «Леммой о рукопожатиях»: сумма степеней всех вершин графа всегда чётна и равна удвоенному количеству рёбер ($$\sum deg(v) = 2|E|$$). 1. Посчитаем сумму степеней: $$1 + 2 + 2 + 3 + 3 = 11$$ 2. Полученное число 11 — нечётное. Согласно лемме, сумма степеней **обязана** быть чётной в любом графе. **Допущение:** В тексте задания 124 на картинке опечатка в условии или в моём первоначальном выводе. Перепроверим: если сумма нечётна, граф построить нельзя. Однако, в заданиях такого типа часто просят найти ошибку. **Важное уточнение:** Если сумма степеней нечётная (как в данном случае: $1+2+2+3+3=11$), то такой граф **не существует**. **Ответ (исправленный): Граф не существует, так как сумма степеней вершин нечётна ($11$), что противоречит лемме о рукопожатиях.** 125. Для графа с 6 вершинами и степенями $1, 1, 2, 2, 3, 3$ сумма равна: $$1+1+2+2+3+3 = 12$$. Это чётное число, значит, граф существует. Вот примеры двух разных (неизоморфных) графов: * **Первый вариант:** Две несвязанные части. Первая часть — треугольник (вершины со степенями 2, 2, 2), вторая часть — «звезда» из 3 вершин, где центр имеет степень 2, а края по 1. Но нам нужны степени 3. Попробуем по-другому. * **Граф А:** Соединим две вершины степени 3 между собой. От каждой из них проведём по одному ребру к вершинам степени 1. Оставшиеся рёбра пустим к вершинам степени 2, образуя циклы или цепочки. :::div .chart-container @chart-1::: :::div .chart-container @chart-2:::