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

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

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

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

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

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