Задача 1: odin Докажите по индукции, что в графе с n вершинами чётное число вершин с нечётной степенью.

Задача 2: odnostor В стране любые два города соединены дорогой с односторонним движением. Доказать, что можно проехать по всем городам, побывав в каждом по одному разу.

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

Задача 4: В некоторой стране каждый город соединён с каждым дорогой с односторонним движением. Докажите, что найдется город, из которого можно добраться в любой другой не более чем с одной пересадкой.

Задача 5: Доказать, что после окончания однокругового турнира по теннису его участников можно выстроить в ряд так, что каждый выиграл у следующего за ним в этом ряду.

Задача 6: В графе с 2n вершинами n² + 1 ребро. Докажите, что в нем есть три вершины, попарно соединённые ребрами.

Задача 7: В компании из n человек среди любых четверых есть знакомый с остальными троими. Доказать, что есть человек, который знает всех остальных.