1 Что такое степень вершины графа? 2 Может ли степень вершины равняться 0? 3 Сформулируйте теорему о сумме степеней вершин. 4 Существует ли граф, в котором только 3 вершины со степенями 1, 2 и 2? Приведите пример такого графа или объясните, почему такого не может быть.

Вопросы

1. Степень вершины графа — это количество рёбер, инцидентных этой вершине.
2. Да, степень вершины может равняться 0. Это означает, что вершина не связана ни с какими другими вершинами (изолированная вершина).
3. Теорема о сумме степеней вершин: Сумма степеней всех вершин графа равна удвоенному числу его рёбер. \( \sum_{v \in V} deg(v) = 2|E| \)
4. Нет, такого графа не существует. Сумма степеней вершин равна \( 1 + 2 + 2 = 5 \). По теореме о сумме степеней вершин, эта сумма должна быть равна удвоенному числу рёбер, то есть чётному числу. Так как 5 — нечётное число, граф с такими степенями вершин невозможен.