ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 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

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .