Остовные деревья с большим количеством висячих вершин: новые нижние оценки через количество вершин степеней 3 и не менее 4

В работе доказывается, что у связного графа $G$, в котором $s$ вершин степени 3 и $t$ вершин степени не менее 4, существует остовное дерево, в котором $\frac25t+\frac15s+\alpha$ висячих вершин, где $\alpha\ge\frac85$. Доказано, что для всех графов, кроме трёх исключений, $\alpha\ge2$. Исключение составляют единственный регулярный граф степени 4 на 6 вершинах и два регулярных графа степени 4 на 8 вершинах (в которых каждое ребро входит в треугольник).
Приводится бесконечная серия примеров графов, содержащих только вершины степеней 3 и 4, для которых максимальное количество висячих вершин в остовном дереве равно $\frac25t+\frac15s+2$. Тем самым, доказана точность всех оценок. Библ. – 12 назв.