Вопрос:

Существует ли граф, в котором 5 вершин, и они имеют степени 1, 2, 2, 3, 3? Может ли количество вершин нечётной степени в каком-нибудь графе равняться: а) 0; б) 1; в) 2; г) 3; д) 4?

Фотография

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

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

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

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