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

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

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

Докажите, что в плоском графе есть вершина, степень которой не превосходит 5.

Можно ли построить три дома, вырыть три колодца и соединить тропинками каждый дом с каждым колодцем так, чтобы тропинки не пересекались?

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

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