Олимпиадные задачи из источника «глава 13. Графы-2» для 5-7 класса - сложность 3 с решениями

20 команд сыграли круговой турнир по волейболу.

Докажите, что команды можно занумеровать числами от 1 до 20 так, что 1-я команда выиграла у 2-й, 2-я – у 3-й, ..., 19-я – у 20-й.

Каждое из рёбер полного графа с 9 вершинами покрашено в синий или красный цвет.

Докажите, что либо есть четыре вершины, все рёбра между которыми – синие, либо есть три вершины, все рёбра между которыми – красные.

Каждое из рёбер полного графа с 17 вершинами покрашено в один из трёх цветов. Докажите, что есть три вершины, все рёбра между которыми – одного цвета.

В связном графе степени четырёх вершин равны 3, а степени остальных вершин равны 4.

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