130 В некотором графе 6 вершин, степени которых равны: a) 2, 2, 3, 3, 4, 4; б) 0, 1, 2 кол 3, 4 том графе?

Ответ: а) да, б) нет

Для графа с n вершинами, степени которых равны d1, d2, ..., dn, должны выполняться два условия:

1. Сумма степеней всех вершин должна быть чётной (так как она равна удвоенному числу рёбер).
2. Максимальная степень любой вершины не должна превышать n - 1 (так как вершина не может быть соединена сама с собой).

а) Степени вершин: 2, 2, 3, 3, 4, 4. Количество вершин: 6.

• Сумма степеней: 2 + 2 + 3 + 3 + 4 + 4 = 18 (чётное число).
• Максимальная степень: 4, и 4 ≤ 6 - 1 = 5.

Оба условия выполняются, поэтому граф с такими степенями может существовать.

б) Степени вершин: 0, 1, 2, 3, 4. Количество вершин: 6 (однако указаны только 5 степеней)

Если предположить, что шестая вершина имеет степень, например, 0 (самый маленький вариант), то: Допустим, что шестая вершина имеет степень 5: Допустим, что шестая вершина имеет степень 6: В любом случае, не хватает данных для того, чтобы полностью определить ситуацию.

• Сумма степеней: 0 + 1 + 2 + 3 + 4 + 5 = 15 (нечётное число)

Одно из условий не выполняется, поэтому граф с такими степенями не может существовать.

Ответ: а) да, б) нет