Trees through specified vertices

We prove a conjecture of Horak that can be thought of as an extension of classical results including Dirac’s theorem on the existence of Hamiltonian cycles. Namely, we prove for 1≤k≤n−21≤k≤n−2 if GG is a connected graph with A⊂V(G)A⊂V(G) such that dG(v)≥kdG(v)≥k for all v∈Av∈A, then there exists a subtree TT of GG such that V(T)⊃AV(T)⊃A and dT(v)≤⌈n−1k⌉ for all v∈Av∈A.