Задача 28:

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

Задача 29:

Можно ли составить решетку, изображенную на рисунке.

а) из 5 ломаных длины 8?

б) из 8 ломаных длины 5? (длина стороны клетки равна 1).

Задача 30:

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

Задача 31:

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

Задача 32:

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

Задача 33:

Каждый из 102 учеников одной школы знаком не менее, чем с 68 другими. Докажите, что среди них найдутся четверо, имеющие одинаковое число знакомых.

Задача 34:

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

Задача 35:

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

Задача 36:

В некоторой стране любые два города соединены либо авиалинией, либо железной дорогой. Докажите, что

а) можно выбрать вид транспорта так, чтобы от любого города можно было добраться до любого другого, пользуясь только этим видом транспорта;

б) из некоторого города, выбрав один из видов транспорта, можно добраться до любого другого города не более, чем с одной пересадкой (пользоваться можно только выбранным видом транспорта);

в) каждый город обладает свойством из пункта б);

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

Задача 37:

Каждое из ребер полного графа с 6 вершинами покрашено в один из двух цветов. Докажите, что есть три вершины, все ребра между которыми – одного цвета.

Задача 38:

Каждое из ребер полного графа с 17 вершинами покрашено в один из трех цветов. Докажите, что есть три вершины, все ребра между которыми – одного цвета.

Задача 39:

Каждое из ребер полного графа с 9 вершинами покрашено в синий или красный цвет. Докажите, что либо есть четыре вершины, все ребра между которыми – синие, либо есть три вершины, все ребра между которыми – красные.

Задача 40:

Каждое из ребер полного графа с 18 вершинами покрашено в один из двух цветов. Докажите, что есть четыре вершины, все ребра между которыми – одного цвета.