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

124. **Ответ: Нет, не существует.** Согласно лемме о рукопожатиях, сумма степеней всех вершин графа всегда чётна и равна удвоенному количеству рёбер ($2E$). В данном случае сумма степеней: $1 + 2 + 3 + 3 + 7 = 16$. Однако, в графе с 5 вершинами максимальная степень любой вершины не может превышать $n - 1$, то есть $5 - 1 = 4$. Вершина со степенью 7 в графе из 5 вершин невозможна. 125. **Ответ: Такой граф не существует.** Сумма степеней вершин: $1 + 1 + 2 + 2 + 3 + 3 = 12$. Сумма чётная, условие леммы о рукопожатиях выполняется. Однако, построить два **неодинаковых** (неизоморфных) графа с такой последовательностью степеней невозможно, так как это простая цепь или цикл с отростками, структура которых жестко определена связями. 126. **Ответ: Нет, не может.** Это следствие леммы о рукопожатиях: в любом графе количество вершин с нечётной степенью всегда чётно. Если бы их количество было нечётным, то общая сумма степеней вершин графа стала бы нечётной, что невозможно.