Задание 6. Можно ли построить граф с 6 вершинами, степени которых равны: 1, 1, 2, 2, 3, 5? Объясни свой ответ

Решение:

• Сумма степеней всех вершин: 1 + 1 + 2 + 2 + 3 + 5 = 14
• Сумма степеней равна 14, что является четным числом.
• Максимальная степень вершины в графе с 6 вершинами равна 5.
• Проверим выполнимость условия Эрдёша — Галлаи.
• Для набора степеней \( d_1 \ge d_2 \ge ... \ge d_n \) существует граф тогда и только тогда, когда сумма степеней четна и для каждого \( k \) от 1 до \( n \) выполняется неравенство:

\[ \sum_{i=1}^{k} d_i \le k(k-1) + \sum_{i=k+1}^{n} \min(k, d_i) \]

Перепишем набор степеней в порядке убывания: 5, 3, 2, 2, 1, 1

k = 1: 5 \(\le\) 0 + min(1, 3) + min(1, 2) + min(1, 2) + min(1, 1) + min(1, 1) = 3 + 1 + 1 + 1 + 1 = 7 (выполняется)

k = 2: 5 + 3 = 8 \(\le\) 2 + min(2, 2) + min(2, 2) + min(2, 1) + min(2, 1) = 2 + 2 + 2 + 1 + 1 = 8 (выполняется)

k = 3: 5 + 3 + 2 = 10 \(\le\) 6 + min(3, 2) + min(3, 2) + min(3, 1) + min(3, 1) = 6 + 2 + 2 + 1 + 1 = 12 (выполняется)

k = 4: 5 + 3 + 2 + 2 = 12 \(\le\) 12 + min(4, 1) + min(4, 1) = 12 + 1 + 1 = 14 (выполняется)

k = 5: 5 + 3 + 2 + 2 + 1 = 13 \(\le\) 20 + min(5, 1) = 20 + 1 = 21 (выполняется)

k = 6: 5 + 3 + 2 + 2 + 1 + 1 = 14 \(\le\) 30 (выполняется)

Условие Эрдёша — Галлаи выполняется, однако вершина степени 5 должна быть соединена со всеми остальными вершинами. Но у нас есть две вершины степени 1, которые могут быть соединены только с вершиной степени 5. То есть построить граф с 6 вершинами, степени которых равны 1, 1, 2, 2, 3, 5 нельзя.

Ответ: Нельзя построить граф с 6 вершинами со степенями 1, 1, 2, 2, 3, 5, так как сумма степеней нечетна