Идея. У дерева с n вершинами n − 1 рёбер, а сумма степеней всех вершин равна удвоенному числу рёбер. Для семи вершин это 12 — по ней проверяем рисунки.
1Число рёбер берём из свойства деревьев (§47*): вершин на одну больше, чем рёбер. Сумма степеней в 2 раза больше числа рёбер, потому что каждое ребро считается у обоих концов.
2Если концов только два, остальные пять вершин должны «пропускать» путь через себя — получается цепочка: у каждой средней вершины степень 2.
3Четыре конца дают в сумме 4, на остальные три вершины остаётся 8: например 3 + 3 + 2. Две вершины степени 3 держат по два конца, средняя соединяет их.
4Шесть концов дают 6, на последнюю вершину остаётся 6 — она соединена со всеми остальными.
Проверка. Пересчитайте рёбра на рисунке: их должно быть 6, и граф не должен распадаться на части.
