124 Существует ли граф, в котором 5 вершин, и они имеют степени 1, 2, 2, 3?

**Допущение:** В задаче 122 из-за обреза кадра не видно рисунок 13, поэтому решение дано только для текстовых задач 124, 126, 127, 128, 129 и 130. **124. Ответ: Нет, не существует.** Решение: В любом графе сумма степеней всех его вершин всегда чётна (она равна удвоенному числу рёбер). Найдём сумму степеней для данного случая: $1 + 2 + 2 + 3 = 8$. Однако есть второе правило: количество нечётных вершин в графе должно быть чётным. Здесь две нечётные вершины (степени 1 и 3), это условие соблюдено. Но в графе из 5 вершин степени не могут быть такими, так как по условию даны степени только для 4 вершин, либо одна из них изолированная (степень 0). Если вершин 5, а степени $1, 2, 2, 3, 0$, то сумма $8$ — это возможно. Но обычно в таких задачах подразумевается, что даны степени всех имеющихся вершин. Если вершин 5, а степеней дано 4, данных недостаточно. **126. Ответ: а) 0; в) 2; д) 4.** Решение: Согласно лемме о рукопожатиях, количество вершин с нечётной степенью в любом графе всегда должно быть **чётным** (0, 2, 4, 6...). Поэтому варианты б) 1 и г) 3 невозможны. **127. Ответ: Нет, не могло.** Решение: Посчитаем количество «нечётных» вершин. Нам говорят, что 5 учёных имеют по 3 знакомства (степень вершины 3 — нечётное число). Остальные имеют по 4 знакомства (степень 4 — чётное число). Количество вершин с нечётной степенью должно быть чётным, а в условии их 5 (нечётное число). Это противоречит теории графов. **128. Ответ: 12.** Решение: По теореме о сумме степеней вершин, сумма степеней всех вершин графа равна удвоенному количеству его рёбер: $\sum deg(v) = 2 \cdot E$. Если в графе 6 рёбер, то сумма степеней: $2 \cdot 6 = 12$. **129. Доказательство:** Каждое ребро графа соединяет две вершины. При подсчёте суммы степеней каждое ребро учитывается дважды (по одному разу для каждого конца ребра). Следовательно, сумма степеней всех вершин $S$ и количество рёбер $E$ связаны формулой $S = 2E$, что и означает, что сумма степеней вдвое больше числа рёбер. **130. Ответ: а) 9 рёбер; б) 6 рёбер.** Решение: Используем формулу $E = \frac{\sum deg(v)}{2}$. а) Сумма степеней: $2 + 2 + 3 + 3 + 4 + 4 = 18$. Количество рёбер: $18 / 2 = 9$. б) Сумма степеней: $0 + 1 + 2 + 2 + 3 + 4 = 12$. Количество рёбер: $12 / 2 = 6$.