На рисунке 13 (с. 80) изображён граф. Найдите степень вершины: а) А; б) Б.

**Ответ: 22. а) 4; б) 3.** **Решение:** 22. Степень вершины — это количество рёбер, которые из неё выходят. По рисунку 13: а) Из вершины А выходят 4 линии. Степень равна 4. б) Из вершины Б выходят 3 линии. Степень равна 3. 23. Степень 0 — это изолированная вершина (точек без линий нет). Степень 1 — вершины, из которых выходит одна линия. Степень 2 — вершины, из которых выходят две линии. (Для точного подсчёта нужно видеть рисунки 19 а и б, но обычно в таких задачах ответ ищется простым подсчётом линий у каждой точки). 24. **Ответ: Нет, не существует.** **Обоснование:** По лемме о рукопожатиях сумма степеней всех вершин графа всегда должна быть чётной (так как каждое ребро считается дважды). Сложим степени: $1 + 2 + 2 + 3 + 3 = 11$. Число 11 — нечётное, значит, такой граф построить невозможно. 25. Чтобы графы были неодинаковыми (неизоморфными), можно по-разному соединить вершины линиями. Например, в первом графе соединить вершины в цепочку $1-2-3-2-1$, а во втором сделать треугольник из вершин со степенью 2 и добавить к ним ответвления. 26. **Ответ: а) 0; б) 1; в) 2; г) 3; д) 4? — Любое чётное количество.** Согласно теории графов, количество вершин с нечётной степенью в любом графе всегда должно быть **чётным**. Поэтому варианты а), в), д) (если под 4 имеется в виду чётное число) возможны, а варианты б) и г) — нет. 27. **Ответ: Нет, не могло.** **Обоснование:** Представим учёных как вершины графа, а знакомства — как рёбра. У пятерых учёных по 3 знакомых (нечётная степень), а у остальных (допустим их $n$) — по 4 знакомых (чётная степень). Общее количество вершин с нечётной степенью равно 5. Но, как мы знаем из задачи №26, количество нечётных вершин обязано быть чётным. 5 — число нечётное, значит, такая ситуация невозможна.