Kriesell, MatthiasMatthiasKriesellSchmidt, Jens M.Jens M.Schmidt2020-10-192020-10-192018-10-01Journal of Graph Theory (2018)http://hdl.handle.net/11420/7594An edge in a k-connected graph G is called k-contractible if the graph G/e obtained from G by contracting e is k-connected. Generalizing earlier results on 3-contractible edges in spanning trees of 3-connected graphs, we prove that (except for the graphs 𝐾Kk𝑘+1 if 𝑘 ∈ 1, 2) (a) every spanning tree of a k-connected triangle free graph has two k-contractible edges, (b) every spanning tree of a k-connected graph of minimum degree at least 3/2 k-1 has two k-contractible edges, (c) for k>3, every DFS tree of a k-connected graph of minimum degree at least 3/2k-3/2 has two k-contractible edges, (d) every spanning tree of a cubic 3-connected graph nonisomorphic to K4 has at least 1/3|V(G)|-1 many 3-contractible edges, and (e) every DFS tree of a 3-connected graph nonisomorphic to K4, the prism, or the prism plus a single edge has two 3-contractible edges. We also discuss in which sense these theorems are best possible.en0364-90242018210111405c0505c40contractible edgeDFS treefoxspanning treeJournal Article10.1002/jgt.22243Other