Идея. Деревья с нужным числом концов удобно строить из цепочки неконцевых вершин, к которой «приклеены» концевые: каждой неконцевой вершине нужна степень не меньше 2.
1Сначала узнаём, сколько вершин не концевые: вычитаем концевые из всех.
2Соединяем три неконцевые вершины в цепочку. Крайним нужно добавить хотя бы по одному концу, чтобы степень была не меньше 2; пусть крайним по 2, средней 1 — всего 5.
3Четыре неконцевые вершины — цепочка из четырёх: у крайних по 2 конца, у средних по 1. Получилось 6 концов.
4По свойству 3 (§47*) рёбер на 1 меньше, чем вершин. Совпадение с рисунком — быстрая проверка, что граф связный и без циклов.
