Задача 6:

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

Задача 7:

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

Задача 8:

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

Задача 9:

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

Задача 10:

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

Задача 11:

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

Задача 12:

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

Задача 13:

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

Задача 14:

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

Задача 15:

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

Задача 16:

В стране 100 городов, некоторые из которых соединены авиалиниями. Известно, что от любого города можно долететь до любого другого (возможно, с пересадками). Докажите, что можно побывать в каждом городе, совершив не более а) 198 перелетов; б) 196 перелетов.