Abstract:
We prove that for every connected graph $G(V,E)$ with no adjacent
vertices of degree 2 there exists a spanning tree with more than $|V|/5$
end vertices. We describe a polynomial algorithm of constructing such a
tree. The constant 1/5 cannot be improved.