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

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

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

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

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

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

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