Задача
Могут ли степени вершин в графе быть равны:
а) 8, 6, 5, 4, 4, 3, 2, 2?
б) 7, 7, 6, 5, 4, 2, 2, 1?
в) 6, 6, 6, 5, 5, 3, 2, 2?
Решение
а) В графе из восьми вершин степень 8 встретиться не может. б) Если есть две вершины, связанные со всеми, то степень каждой из остальных вершин не меньше 2. в) Сумма степеней вершин должна быть чётной.
Ответ
а)-в) Не может.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь
Комментариев нет