Построение остовного дерева графа с большим количеством листьев

Известно, что в графе на $n$ вершинах с минимальной степенью 4 существует остовное дерево, содержащее не менее $\frac25\cdot n$ листьев [4], что является асимптотически точной оценкой для таких графов. В нашей работе приводится полиномиальный алгоритм, находящий в графе с $k$ вершинами степени хотя бы четыре и $k'$ вершинами степени три, остовное дерево с количеством висячих вершин, по крайней мере $\lceil\frac25\cdot k+\frac2{15}\cdot k'\rceil$. Библ. – 13 назв.