В графе 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.