Spanning Trees with Vertices Having Large Degrees

Let G be a connected simple graph, and let f be a mapping from V ( G ) to the set of integers. This paper is concerned with the existence of a spanning tree in which each vertex v has degree at least f ( v ) . We show that if | Γ G ( S ) | − f ( S ) + | S | ≥ 1 for any nonempty subset S ⊆ L , then a connected graph G has a spanning tree such thatd T ( x ) ≥ f ( x )for all x ∈ V ( G ) , whereΓ G ( S )is the set of neighbors v of vertices in S with v ∉ S , L = { x ∈ V ( G ) : f ( x ) ≥ 2 } , andd T ( x )is the degree of x in T . This is an improvement of several results, and the condition is best possible.