Задача 1: Доказать, что во всяком дереве есть висячие вершины.

Задача 2: Может ли дерево содержать ровно одну висячую вершину?

Задача 3: Нарисуйте все возможные деревья с шестью вершинами. Докажите, что других нет.

Задача 4: Доказать, в дереве количество вершин на 1 больше количества рёбер.

Задача 5: В дереве есть 8 вершин степени три, 10 вершин степени 4 и несколько висячих вершин. Других вершин нет. Найти число висячих вершин.

Задача 6: У царя Гвидона было три сына. Из его потомков 100 имели по два сына, а остальные умерли бездетными. Сколько потомков было у царя Гвидона?

Задача 7: Лес состоит из k деревьев. Найти, на сколько в этом лесу вершин больше, чем рёбер.

Задача 8: Доказать, что в связном графе с циклами вершин не больше чем рёбер.

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

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

Решение: Указание: Рассматриваем государство со следующими системами дорог. (Рисуем различные связные графы с циклами). Какие дороги можно закрывать, не нарушая связность системы?

Задача 11: В связном графе B вершин и P рёбер. Сколько рёбер надо удалить, чтобы получить скелет этого графа?

Решение: Указание: Надо доказать, что если ребро входит хоть в один цикл, то оно не является мостом.

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

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