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

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

В стране <i>n</i> городов. Между каждыми двумя городами установлено воздушное сообщение одной из двух авиакомпаний. Докажите, из этих двух авиакомпаний хотя бы одна такова, что что из любого города можно попасть в любой другой рейсами только этой авиакомпании.

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

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

На плоскости дано 100 окружностей, составляющих связную (то есть не распадающуюся на части) фигуру.

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

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

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

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

Докажите, что для плоского графа справедливо неравенство  2<i>E</i> ≥ 3<i>F</i>.

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

Пусть связный плоский граф с <i>V</i> вершинами и <i>E</i> рёбрами разрезает плоскость на <i>F</i> кусков. Докажите формулу Эйлера:  <i>V – E + F</i> = 2.