Задача 1: Какие из изображенных графов является деревом?

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

б) Докажите, что в дереве любые две вершины соединены ровно одним простым путем.

Задача 3: а) Гусеница летом ползет по березе (никакие ветки и листья березы не пересекаются и не соприкасаются) так, что на каждой развилке веток она ползет по любой из веток, кроме той, по которой приползла к этой развилке. Доказать, что рано или поздно она выползет на лист.

б) Докажите, что в дереве есть вершина, из которой выходит ровно одно ребро (такая вершина называется висячей или листом);

в) Докажите, что в дереве есть хотя бы две висячие вершины.

Задача 4: В графе все вершины имеют степень 3. Докажите, что в нем есть цикл.

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

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

Задача 5: Сколько было бревен, если 52-мя распилами из них получили 72 полена?

Задача 6: а) В стране Древляндии 101 город, и некоторые из них соединены дорогами. При этом любые два города соединяет ровно один путь. Сколько в этой стране дорог?

б) Докажите, что в дереве число вершин на 1 больше числа ребер.

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

Задача 8: Волейбольная сетка имеет форму прямоугольника размером 50 × 600 клеток. Какое наибольшее число веревочек можно перерезать так, чтобы сетка не распалась на куски?

Задача 9: Есть такая сеть метро, что с любой станции можно добраться до любой другой не поднимаясь на поверхность. Докажите, что мы можем закрыть какую-то одну станцию без права проезда через нее так, чтобы и после этого можно было бы добраться с любой станции на любую другую.

Задача 11: Посылку (куб) зашили на почте в мешковину (в форме куба). Играют двое (получившие посылку). За один ход разрешается сделать разрез вдоль любого ребра куба (по которому еще не делался разрез). Проигрывает тот, после хода которого мешковина распадается на две части. Кто может выиграть?

Задача 12: В поселке 100 домов. Какое наибольшее число непересекающихся заборов можно построить так, чтобы каждый забор огораживал хотя бы один дом, и никакие два забора не огораживали бы одну и ту же совокупность домов?

Задача 13: В стране 30 городов, причем каждый соединен с каждым дорогой. Какое наибольшее число дорог можно закрыть на ремонт так, чтобы из каждого города можно было проехать в каждый.

Задача 14: Вдоль границ клеток шахматной доски положили спички. Сколько спичек необходимо убрать, чтобы ладья могла добраться с любого поля на любое?

Задача 15: В ныне суверенном Зурбагане сеть железных дорог устроена так: все города стоят на кольце; кроме того, столица соединена отдельными ветками с каждым из городов, кроме соседей по кольцу. Правительство Зурбагана разбило сеть на участки между соседними городами и постановило разделить эти участки между двумя компаниями так, чтобы можно было проехать между любыми двумя городами как по дорогам только первой компании, так и по дорогам только второй компании. Можно ли выполнить постановление правительства?