More on foxes
Matthias Kriesell, Jens M. Schmidt · Journal of Graph Theory · 2018
Abstract An edge in a k‐connected graph G is called k‐contractible if the graph 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 if ) (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 has two k‐contractible edges, (c) for , every DFS tree of a k‐connected graph of minimum degree at least has two k‐contractible edges, (d) every spanning tree of a cubic 3‐connected graph nonisomorphic to K4 has at least 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.