28 Придумайте и нарисуйте 3 неодинаковых графа, в каждом из которых по 6 рёбер. Найдите сумму степеней всех вершин каждого из этих графов.

Задание 28

Согласно теореме о рукопожатиях, сумма степеней всех вершин графа равна удвоенному числу рёбер. В данном случае число рёбер равно 6, значит, сумма степеней во всех графах будет \( 2 \times 6 = 12 \).

Придумаем три неодинаковых графа с 6 ребрами:

Граф 1:

• Состоит из 6 вершин, соединенных последовательно, и одного ребра, соединяющего первую и последнюю вершины (цикл \( C_6 \)).
• Ребра: (1,2), (2,3), (3,4), (4,5), (5,6), (6,1).
• Все вершины имеют степень 2.
• Сумма степеней: \( 6 \times 2 = 12 \).

Граф 2:

• Состоит из 5 вершин, где одна вершина имеет степень 3, а остальные 4 вершины имеют степень 2 (кроме одной, которая имеет степень 1).
• Ребра: (1,2), (1,3), (1,4), (2,3), (4,5), (5,1)
• Степени: deg(1)=4, deg(2)=2, deg(3)=2, deg(4)=2, deg(5)=2, deg(6)=0 (если 6 вершин)
• Допустим, у нас 6 вершин и 6 ребер. Пример:
• Вершины: 1, 2, 3, 4, 5, 6.
• Ребра: (1,2), (2,3), (3,4), (4,1), (1,5), (5,6).
• Степени: deg(1)=3, deg(2)=2, deg(3)=2, deg(4)=2, deg(5)=2, deg(6)=1.
• Сумма степеней: \( 3 + 2 + 2 + 2 + 2 + 1 = 12 \).

Граф 3:

• Состоит из 4 вершин, где 3 вершины соединены друг с другом (полный граф \( K_3 \)), и еще одна вершина присоединена к одной из вершин \( K_3 \). Остальные 2 вершины изолированы.
• Для 6 ребер:
• Вершины: 1, 2, 3, 4, 5, 6.
• Ребра: (1,2), (1,3), (2,3), (1,4), (2,5), (3,6).
• Степени: deg(1)=3, deg(2)=3, deg(3)=3, deg(4)=1, deg(5)=1, deg(6)=1.
• Сумма степеней: \( 3 + 3 + 3 + 1 + 1 + 1 = 12 \).

Ответ: Сумма степеней всех вершин в каждом из этих графов равна 12.