Spanning trees and spanning Eulerian subgraphs with small degrees

Liu and Xu (1998) and Ellingham, Nam and Voss (2002) independently showed that every kk-edge-connected simple graph GG has a spanning tree TT such that for each vertex vv, dT(v)≤⌈d(v)k⌉+2. In this paper we show that every kk-edge-connected graph GG has a spanning tree TT such that for each vertex vv, dT(v)≤⌈d(v)−2k⌉+2; also if GG has kk edge-disjoint spanning trees, then TT can be found such that for each vertex vv, dT(v)≤⌈d(v)−1k⌉+1. This result implies that every (r−1)(r−1)-edge-connected rr-regular graph (with r≥4r≥4) has a spanning Eulerian subgraph whose degrees lie in the set {2,4,6}{2,4,6}; also reduces the edge-connectivity needed for some theorems due to Barát and Gerbner (2014) and Thomassen (2008, 2013). Moreover these bounds for finding spanning trees are sharp.