Дано:
Граф с 5 вершинами, степени которых равны 4, 1, 3, 2, 4.
Найти:
Доказать, что не существует такого графа без петель и кратных рёбер.
Решение:
1. По формуле для степени графа, сумма степеней всех вершин должна быть равна удвоенному числу рёбер:
S = 2E, где S — сумма степеней, E — число рёбер.
2. Посчитаем сумму степеней:
S = 4 + 1 + 3 + 2 + 4 = 14.
3. Теперь найдём количество рёбер:
E = S / 2 = 14 / 2 = 7.
4. Проверим возможность существования такого графа:
- В графе с 5 вершинами максимальное количество рёбер Emax = 5 * (5 - 1) / 2 = 10.
- При этом в графе с 5 вершинами не может быть вершины со степенью больше 4, так как каждая вершина может соединяться не более чем с 4 другими вершинами.
5. Рассмотрим вершину со степенью 1. Она может соединяться только с одной вершиной, что оставляет только 4 вершины для остальных рёбер.
6. Вершины со степенями 4, 4, и 3 требуют много рёбер. Однако:
- Если две вершины имеют степень 4, каждая из них должна соединяться с 4 разными вершинами, что в итоге требует 8 рёбер (недопустимо).
7. Таким образом, граф с указанными степенями не может существовать, так как условия не выполняются.
Ответ:
Не существует графа без петель и кратных рёбер, у которого 5 вершин со степенями 4, 1, 3, 2, 4.