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

Решение:

По теореме о сумме степеней вершин графа, сумма степеней всех вершин графа равна удвоенному числу его рёбер. В каждом из предложенных графов количество рёбер равно 6. Следовательно, сумма степеней всех вершин в каждом графе будет:

\( S = 2 × 6 = 12 \).

Граф 1: Полный граф K₄ с одним изолированным ребром (5 вершин).

Этот граф имеет 4 вершины, соединенные между собой (степени 3, 3, 3, 3), и еще две вершины, соединенные ребром (степени 1, 1). Всего 6 вершин, 3+3+3+3+1+1 = 14. Это неверно.

Граф 1: Полный граф K₄.

Этот граф имеет 4 вершины, каждая из которых соединена с тремя другими. Число рёбер: \( \frac{4 × 3}{2} = 6 \). Степени вершин: 3, 3, 3, 3. Сумма степеней: \( 3 + 3 + 3 + 3 = 12 \).

Граф 2: Цикл C₆.

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

Граф 3: Звезда (центральная вершина, соединенная с 5 другими).

Этот граф имеет 6 вершин. Одна центральная вершина соединена с 5 другими. Число рёбер: 5. Для получения 6 рёбер добавим ребро между двумя из 5 периферийных вершин. Степени вершин: 5 (центральная), 3 (две вершины), 2, 2, 2. Сумма степеней: \( 5 + 3 + 3 + 2 + 2 + 2 = 17 \). Это неверно.

Граф 3: Звезда (центральная вершина, соединенная с 5 другими).

Этот граф имеет 6 вершин. Одна центральная вершина соединена с 5 другими. Число рёбер: 5. Не подходит.

Граф 3: Граф Петерсена (часть) или другой граф с 6 ребрами.

Граф 3: Два треугольника, соединенные ребром.

Этот граф имеет 6 вершин. Две вершины соединены ребром, и каждая из них является вершиной треугольника. Общее число рёбер: 2 (основное ребро) + 2 (в первом треугольнике) + 2 (во втором треугольнике) = 6. Степени вершин: 3, 3, 2, 2, 2, 2. Сумма степеней: \( 3 + 3 + 2 + 2 + 2 + 2 = 14 \). Неверно.

Граф 3: Две вершины, каждая из которых соединена с тремя другими.

Этот граф имеет 6 вершин. Две вершины (A и B) соединены с тремя другими (C, D, E). Например, A соединена с C, D, E; B соединена с C, D, E. Тогда у A и B степени 3. У C, D, E степени 2. Всего 5 рёбер. Для 6 рёбер можно добавить ребро между A и B.

Граф 3: Две вершины, каждая из которых соединена с тремя другими, плюс ребро между ними.

Пусть вершины A, B, C, D, E, F. A соединена с B, C, D. B соединена с A, E, F. Число рёбер: 1 (A-B) + 2 (A-C, A-D) + 2 (B-E, B-F) = 5. Нужно 6. У A степень 3, у B степень 3. У C, D, E, F степень 1. Сумма степеней = 3+3+1+1+1+1 = 10. Неверно.

Граф 3: Граф, состоящий из пути P₅ и одной изолированной вершины.

Путь P₅ имеет 5 вершин и 4 ребра. Добавим еще 2 ребра. Например, вершина 1 связана с 2, 2 с 3, 3 с 4, 4 с 5. Это 4 ребра. Добавим ребро 1-3 и 2-4. Всего 6 ребер. Степени: 1 (2), 2 (3), 3 (3), 4 (2), 5 (1). Сумма степеней = 2+3+3+2+1 = 11. Неверно.

Граф 3: Один путь из 4 вершин и два отдельных ребра.

Вершины 1-2-3-4. Ребра (1,2), (2,3), (3,4). Добавим ребро (1,3) и (2,4). Всего 5 ребер. Нужно 6. Добавим ребро (5,6).

Граф 3: Две звезды с 3 лучами, соединенные между собой.

Две звезды по 4 вершины (центр + 3 луча). Всего 8 вершин. 3+3=6 ребер. Нужно 6 ребер.

Граф 3: Граф, состоящий из двух K₃ (треугольников), соединенных одним ребром.

Вершины V1, V2, V3 образуют треугольник (3 ребра). Вершины V4, V5, V6 образуют треугольник (3 ребра). Соединим V1 и V4 ребром. Общее число рёбер: 3 + 3 + 1 = 7. Не подходит.

Граф 3: Соединим 4 вершины в квадрат, и добавим две диагонали.

Вершины 1, 2, 3, 4. Ребра (1,2), (2,3), (3,4), (4,1) — 4 ребра. Диагонали (1,3), (2,4) — 2 ребра. Всего 6 ребер. Степени всех вершин: 4, 4, 4, 4. Сумма степеней: \( 4 \times 4 = 16 \). Не подходит.

Граф 3: Треугольник, из каждой вершины которого выходит ребро.

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

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