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

Question

Вопрос:

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

Фотография

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

Accepted Answer

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

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

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

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