Вопрос:

Существует ли граф, в котором 5 вершин, и они имеют степени 1, 2, 2, 3, 3? Изобразите такой граф или объясните, почему это невозможно.

Фотография

Ответ ассистента

Для решения этой задачи воспользуемся «Леммой о рукопожатиях»: сумма степеней всех вершин любого графа всегда является чётным числом (так как каждое ребро соединяет две вершины и учитывается дважды). 1. Найдём сумму степеней вершин: $1 + 2 + 2 + 3 + 3 = 11$. 2. Полученное число 11 — нечётное. Следовательно, такой граф существовать не может, так как сумма степеней вершин должна быть чётной. **Ответ: Нет, не существует.**

Другие решения

Что ещё задавали пользователи