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

Question

Вопрос:

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

Фотография

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

Accepted Answer

124. Нет, такой граф не существует. Потому что сумма степеней всех вершин в любом графе всегда является четным числом и равна удвоенному количеству ребер. Это называется леммой о рукопожатиях. Давайте посчитаем сумму степеней, которые нам даны: $1 + 2 + 2 + 3 + 3 = 11$. Число 11 — нечетное. Так как сумма степеней нечетная, то такого графа не существует. 125. Сумма степеней вершин: $1 + 1 + 2 + 2 + 3 + 3 = 12$. Это четное число, поэтому такие графы могут существовать. Первый граф: :::div .chart-container @chart-1::: Второй граф: :::div .chart-container @chart-2:::

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

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

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