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

Сумма степеней вершин должна быть четной, чтобы граф существовал. В данном случае сумма степеней равна $$1 + 2 + 2 + 3 = 8$$. Поскольку сумма четная, такой граф может существовать. Изобразим граф: Предположим, что вершины имеют степени 1, 2, 2, 3. Обозначим вершины $$v_1, v_2, v_3, v_4, v_5$$. Пусть $$deg(v_1) = 1, deg(v_2) = 2, deg(v_3) = 2, deg(v_4) = 3, deg(v_5) = x$$. Осталось определить степень вершины $$v_5$$. Если $$v_1$$ соединена с $$v_4$$, то у $$v_4$$ остается 2 ребра. $$v_2$$ и $$v_3$$ можно соединить с $$v_4$$. В таком случае, чтобы сумма степеней была 8, степень вершины $$v_5$$ должна быть 0. Таким образом граф существует.