Задача 31076

Темы:    [ Степень вершины ] [ Четность и нечетность ]

Сложность: 2+ Классы: 6,7,8

Условие

Могут ли степени вершин в графе быть равны:
  а) 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.

  в) Сумма степеней вершин должна быть чётной.

Ответ

а)-в) Не может.

Источники и прецеденты использования

книга
Автор	Иванов С.В.
Название	Математический кружок
глава
Номер	5
Название	Графы
Тема	Теория графов
задача
Номер	08