Задача 17:

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

Задача 18:

В квадрате отметили 20 точек и соединили их непересекающимися отрезками друг с другом и с вершинами квадрата так, что квадрат разбился на треугольники. Сколько получилось треугольников?

Задача 19:

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

Задача 20:

Для плоского связного графа справедливо неравенство E ≤ 3V – 6.

Задача 21:

Докажите, что для любого плоского графа (в том числе и несвязного) справедливо неравенство E ≤ 3V – 6.

Задача 22:

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

Задача 23:

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

Задача 24:

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

Задача 25:

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

Задача 26:

Каждое ребро полного графа с 11 вершинами покрашено в один из двух цветов: красный или синий. Докажите, что либо «красный», либо «синий» граф не является плоским.

Задача 27:

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