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

Question

Вопрос:

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

Фотография

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

Accepted Answer

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

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

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

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