Задача 1: На плоскости нарисованы вершины графа, пронумерованные числами от 2 до 30. При этом две вершины с номерами a и b соединены ребром только в том случае, если одно из чисел a или b делится на другое. Сколько компонент связности имеет этот граф?

Решение: 5 компонент – 29, 23, 19, 17, все остальные

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

Решение: Рассмотрим два произвольных города и предположим, что они не соединены путем, то есть такой последовательностью дорог, в которой начало очередной дороги совпадает с концом предыдущей. Каждый из этих двух городов по условию соединен не менее, чем с 7 другими; при этом все упомянутые города различны – ведь если какие-то два из них совпадают, то есть путь, соединяющий исходные города.

Таким образом, мы указали не менее 16 городов. Противоречие.

Задача 3: Степень каждой вершины связного графа не менее 100. Одно ребро выкинули. Может ли получиться несвязный граф?

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

Решение: Если удалено ребро AB, то нам достаточно доказать, что и после этого есть путь из A в B. Если это не так, то в компоненте связности, содержащей A, все вершины, кроме A, – чётные. Ровно одной нечётной вершины быть не может.

Задача 5: В компьютерной сети от сервера отходит 21 провод, от остальных компьютеров – по 4 провода, а от принтера – один провод. Докажите, что с сервера можно послать документ на принтер.

Решение: Рассмотрим компоненту связности, содержащую сервер. Нам нужно доказать, что она содержит также и принтер. Предположим противное. Тогда в этой компоненте связности из одной вершины (сервера) выходит 21 ребро, а из всех остальных вершин – по 20 ребер. Таким образом в этом графе (компоненте связности) ровно одна нечётная вершина. Противоречие!

Задача 6: В Метрополисе 12 станций метро, соединённых 56 перегонами (две станции соединяются не более чем одним перегоном). Докажите, что метрополитен связен.

Решение: Докажем, что со станции 1 можно попасть на станцию 2. Если нельзя, то на непересекающихся 11-ти маршрутах 1–2, 1–3–2, 1–4–2, 1–5–2,…, 1–12–2 не хватает хотя бы по одному ребру. Но до полного графа не хватает всего 10 рёбер.