Запишите по возрастанию степени всех вершин графа (рис. 19).

1. **Ответ: 2, 3, 3, 4, 4, 4, 4, 5, 5.** **Решение:** Степень вершины — это количество рёбер, которые из неё выходят. Посчитаем их для каждой вершины на Рис. 19: - Нижняя левая вершина: 3 рёбра; - Нижняя правая: 4 рёбра; - Самая правая: 3 рёбра; - Верхняя правая: 4 рёбра; - Самая верхняя: 2 рёбра; - Верхняя левая: 4 рёбра; - Центральная левая: 4 рёбра; - Центральная нижняя: 5 рёбер; - Центральная верхняя: 5 рёбер. Упорядочим по возрастанию: 2, 3, 3, 4, 4, 4, 4, 5, 5. 2. **Ответ: Случаи 1 и 2 существуют.** **Решение:** Используем лемму о рукопожатиях: сумма степеней всех вершин равна удвоенному количеству рёбер (всегда чётное число). 1) $5 \times 3 = 15$. Нечётно — граф **не существует**. 2) $8 \times 2 = 16$. Чётно — граф **существует** (это обычный цикл из 8 вершин). 3) В графе из 8 вершин максимальная степень вершины может быть равна 7 (связь со всеми остальными). Степень 8 невозможна без петель — **не существует**. 3. **Ответ: 6 задач.** **Решение:** Общее количество решённых задач всеми учениками: $24 \times 5 = 120$ (решений). Пусть $x$ — количество задач в контрольной. Каждую задачу решили 20 человек. Значит, общее количество решений также равно $20 \times x$. Составим уравнение: $20x = 120$ $x = 120 \div 20$ $x = 6$ 4. **Ответ: 2, 4.** **Решение:** Цикл — это путь, в котором первая и последняя вершины совпадают, а рёбра не повторяются. 1) abafgkeda: начинается на 'a', заканчивается на 'a', но ребро 'ab' проходится дважды — **не цикл**. 2) abcadea: начинается и заканчивается на 'a', все рёбра разные — **цикл**. 3) fghf: нет ребра между 'g' и 'h' на рисунке — **не путь**. 4) aeafa: начинается и заканчивается на 'a', рёбра разные (треугольник) — **цикл**. 5) kebafgk: конечные точки разные — **не цикл**.