Задачи и упражнения

1. Докажите, что однородный граф третьей степени содержит цикл.

2. В некотором государстве 201 город, некоторые из которых соединены дорогами гак, что любые два города соединяет ровно один путь. Сколько дорог в государстве?

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

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

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

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

7. Докажите, что среди 7 деревьев, каждое из которых имеет 6 вершин, есть два изоморфных.

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

9. Постройте все различные (не изоморфные) деревья с восемью вершинами.

10. Докажите, что любое дерево (с более чем двумя вершинами) можно рассматривать как двудольный граф. Какие деревья являются полными двудольными графами?