Изобразите такой граф или объясните, почему это невозможно.

Решение:

По условию задачи, граф должен иметь 6 вершин со степенями 1, 1, 2, 2, 3, 3. Согласно лемме о рукопожатиях (сумма степеней всех вершин графа равна удвоенному числу его ребер), сумма степеней вершин равна \( 1 + 1 + 2 + 2 + 3 + 3 = 12 \). Это четное число, что соответствует теореме.

Теперь попытаемся построить такой граф:

1. Вершины с первой степенью (1 и 1) должны быть соединены только с одной другой вершиной. Они не могут быть соединены друг с другом, так как тогда их степень была бы 2.

2. Вершины со степенью 3 должны быть как-то связаны с остальными вершинами.

3. В графе обязательно должны быть вершины с нечётной степенью. Если в графе есть вершины с нечётной степенью, их должно быть чётное количество. В нашем случае их две (степени 1, 1, 3, 3).

Пример построения такого графа:

Пусть вершины будут обозначены как v1, v2, v3, v4, v5, v6.

Степени: deg(v1)=1, deg(v2)=1, deg(v3)=2, deg(v4)=2, deg(v5)=3, deg(v6)=3.

Ребра:

• Соединим v1 и v5.
• Соединим v2 и v5.
• Соединим v6 и v3.
• Соединим v6 и v4.
• Соединим v5 и v3.
• Соединим v6 и v4. (Повторение, это неверно)

Давайте попробуем иначе:

Вершины с нечетной степенью: v1(1), v2(1), v3(3), v4(3).

Вершины с четной степенью: v5(2), v6(2).

1. Соединим v1 с v3.

2. Соединим v2 с v4.

3. Соединим v3 с v5.

4. Соединим v3 с v6.

5. Соединим v4 с v5.

6. Соединим v4 с v6.

Проверим степени:

deg(v1) = 1 (v1-v3)

deg(v2) = 1 (v2-v4)

deg(v3) = 3 (v3-v1, v3-v5, v3-v6)

deg(v4) = 3 (v4-v2, v4-v5, v4-v6)

deg(v5) = 2 (v5-v3, v5-v4)

deg(v6) = 2 (v6-v3, v6-v4)

Степени вершин: 1, 1, 3, 3, 2, 2. Это соответствует условию.

Ответ: Граф может существовать. Пример построения представлен выше.