В графе 5 вершин. Четыре из них имеют степени 1,2,3, и 4. Какую степень может иметь пятая вершина?

Решение в рамках простого графа на 5 вершинах (без петель и кратных дуг).

Дано: степени вершин равны 1, 2, 3, 4 и неизвестная d.

1. По сумме степеней: сумма степеней равна 2|E| и, следовательно, чётна. 1 + 2 + 3 + 4 + d = 10 + d должно быть чётным ⇒ d чётное. Возможные значения d: 0, 2, 4 (не больше 4, так как всего 5 вершин).

2. Не бывает isolated вершины в графе, в котором есть вершина степени 4 (она соединена со всеми остальными четырьмя вершинами). Значит вершина степени 0 невозможна. Поэтому d ≠ 0.

3. Рассмотрим вариант d = 4. Тогда две вершины имели бы степень 4. Но если одна из остальных вершин имеет степень 1, она должна быть соседней и с обеими вершинами степени 4, что сделало бы её степень как минимум 2. Противоречие. Поэтому d ≠ 4.

4. Остался единственный возможный вариант: d = 2.

Значит, пятая вершина может иметь степень 2.

Пояснение наглядным примером: Пусть вершины A, B, C, D, E имеют степени 4, 3, 2, 2, 1 соответственно (то есть d = 2). Построим граф так:

• Соединяем A с каждой другой вершиной: AB, AC, AD, AE. Теперь A имеет степень 4, E — 1.
• Чтобы B имел степень 3, добавим ребра BC и BD. Получаем: степени A=4, B=3, C=2 (одинаковая сеть: AC и BC), D=2 (AD и BD), E=1 (AE).

Итак, ответ: 2.