Вопрос:

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

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

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

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

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

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