125 Придумайте и нарисуйте два неодинаковых графа, в каждом из которых 6 вершин со степенями 1, 1, 2, 2, 3, 3.

**Ответ: ниже предложены два варианта графа с заданными степенями вершин.** Степень вершины — это количество ребер, которые из неё выходят. Нам нужно, чтобы в графе были вершины со следующими «связями»: две вершины по 1 ребру, две — по 2 ребра и две — по 3 ребра. Общая сумма степеней равна $1+1+2+2+3+3 = 12$, значит, в графе будет $12 / 2 = 6$ ребер. Вот два способа соединить такие вершины: 1. **Вариант А (линейно-кольцевой):** Представь цепочку: вершина(1) — вершина(3) — вершина(2) — вершина(2) — вершина(3) — вершина(1). * Вершины на концах имеют степень 1. * Внутренние вершины имеют степени 3, 2, 2, 3. 2. **Вариант Б (с циклом и «хвостами»):** Сделаем треугольник из вершин со степенями (3, 3, 2). К двум вершинам этого треугольника (тем, у которых степень 3) присоединим по одной отдельной вершине (степени 1). Оставшаяся шестая вершина должна иметь степень 2 — её можно вставить в одну из сторон треугольника, превратив её в путь из двух ребер. Поскольку графически изобразить это здесь сложно, я опишу структуру: * **Граф 1:** Путь $A-B-C-D-E-F$, где мы добавляем дополнительные ребра, чтобы получить нужные степени. Например: ребра (1-2), (2-3), (3-4), (4-5), (5-6) и (2-5). Проверим степени: $V_1=1, V_2=3, V_3=2, V_4=2, V_5=3, V_6=1$. Это в точности наш набор: 1, 1, 2, 2, 3, 3. * **Граф 2:** Два треугольника, соединенных одной общей вершиной, не подойдут по количеству вершин. Возьмем цикл из 4 вершин (квадрат) $1-2-3-4-1$ и добавим две «антенны» к противоположным углам. Ребра: (1-2), (2-3), (3-4), (4-1), (1-5), (3-6). Степени: $V_1=3, V_2=2, V_3=3, V_4=2, V_5=1, V_6=1$. Набор совпадает.