Вопрос:

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

Фотография

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

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

Похожие задачи

Посмотри похожие решения — вдруг одно из них подойдёт тебе

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

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