Spanning trees without adjacent vertices of degree 2

Kasper Szabo Lyngsie, Martin Merker

Published 2018-01-22Version 1

Albertson, Berman, Hutchinson, and Thomassen showed in 1990 that for every natural number $k$ there exists a $k$-connected graph of which every spanning tree contains vertices of degree 2. Using a result of Alon and Wormald, we show that there exists a natural number $d$ such that every graph of minimum degree at least $d$ contains a spanning tree without adjacent vertices of degree 2. Moreover, we prove that every graph with minimum degree at least 3 has a spanning tree without three consecutive vertices of degree 2.