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

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

Докажите, что связный граф с 2<i>n</i> нечётными вершинами можно нарисовать, оторвав карандаш от бумаги ровно  <i>n</i> –1  раз и не проводя никакое ребро дважды.

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

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

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

В стране Озёрная семь озер, соединённых между собой десятью непересекающимися каналами, причём от каждого озера можно доплыть до любого другого. Сколько в этой стране островов?