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

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

Решение: Индукционный переход. Уберём произвольный город A. По индукционному предположению оставшуюся часть можно обойти, пусть этот путь начинается с города B. Если дорога между A и B ведёт в B, то можно из A переехать в B, и проехать оттуда по оставшимся городам. Если же эта дорога ведёт в A, то рассмотрим последний город на пути (C). Если дорога между A и C ведёт в A, то искомый маршрут – B–…–C–A. Иначе – рассмотрим первый город на пути, в который ведёт дорога из A. (назовём его D, а предыдущий – E) и воспользуемся маршрутом B–…–E–A–D–…–C.

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

Решение: Переход. Уберём произвольный город A. По индукционному предположению теперь можно добраться от одного города в другой с помощью лодочки или кареты. Пусть, для определённости, можно добраться с помощью лодочки). Если из A можно добраться водным путём хотя бы в один город, то можно добраться и до любого другого города. Если же из A во все остальные города ездит карета, то из любого города до любого другого можно добраться сухопутным путём через город A.

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

Решение: Индукция по числу городов. База очевидна. Для доказательства индукционного перехода удалим сначала один из городов (назовём его A). В силу индукционного предположения есть город B с требуемым свойством. Если из B в A ведёт дорога, то город B искомый. Если же дорога ведёт из A в B, то рассмотрим все города, в которые ведёт дорога из B. Если хоть из одного из них ведёт дорога в A, то город B снова искомый. В противном случае искомым является город A.

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

Решение: Это переформулировка задачи о существовании пути в полном ориентированном графе.

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

Решение: Индукционный переход. Пусть утверждение верно для произвольного графа с 2n вершинами. Докажем, что оно верно и для графа с 2(n + 1) вершинами. Рассмотрим произвольные две вершины A и B. Если существует вершина C, из которой идут рёбра и в A и в B, то треугольник нашёлся. Если же такой вершины нет, то из вершин A и B ведёт не более 2n рёбер. Поэтому, если убрать из графа вершины A и B, то останется 2n вершин и не менее чем (n + 1)² – 2n = n² + 1 рёбер и по индукционному предположению в оставшейся части графа найдётся треугольник.

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