Деревья и обход графа

Дерево — связный граф без циклов. В дереве с \(n\) вершинами ровно \(n - 1\) рёбер, и между любыми двумя вершинами есть единственный путь. Если к дереву добавить ребро, появится цикл; если удалить ребро, граф распадётся на две части.

Пример. Между 8 деревнями нужно проложить дороги так, чтобы из любой деревни можно было доехать в любую, а дорог было как можно меньше. Сколько дорог понадобится?
Решение. Граф должен быть связным, а наименьшее число рёбер у связного графа — у дерева: \(8 - 1 = 7\) дорог.

Обход по рёбрам. Обойти все рёбра связного графа, проходя по каждому ровно один раз, можно, если вершин нечётной степени нет (тогда путь замкнутый) или их ровно две (путь начинается в одной из них и заканчивается в другой). Именно это правило объясняет задачу о кёнигсбергских мостах: там все четыре вершины имели нечётную степень.

Пример. Степени вершин графа: 2, 3, 4, 3, 2. Можно ли нарисовать его, не отрывая карандаша и не проводя дважды одну линию?
Решение. Нечётных вершин две (степени 3 и 3), поэтому можно: начать нужно в одной из них, закончить — в другой.