Spanning trees of bounded degree (Q5947942)

A classical theorem of Dirac says that a graph \(G= (V,E)\) with minimum degree at least \(|V|/2\) is Hamiltonian. As a corollary Ore showed that if the sum of the degrees of each pair of non-adjacent vertices is at least \(|V|-1\) then \(G\) has a Hamilton path. Such a path is just a spanning tree for \(G\) with small maximum degree. It is natural to ask to guarantee the existence of a spanning tree with a predetermined maximum degree \(k\). The paper discusses this question and gives a description of the structure of graphs satisfying \[ \sum_{v\in I} \text{degree}(v)\geq|V|-1 \] for every \(k\)-element independent set of vertices of \(G\).