Задача 31086

Темы:    [ Ориентированные графы ] [ Принцип Дирихле (прочее) ]

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

Условие

В ориентированном графе 101 вершина. У каждой вершины число входящих и число выходящих рёбер равно 40.

Доказать, что из каждой вершины можно попасть в любую другую, пройдя не более чем по трём ребрам.

Решение

См. задачу 30830 б).

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

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