Every DFS Tree of a 3‐Connected Graph Contains a Contractible Edge
Amr Elmasry, Kurt Mehlhorn, Jens M. Schmidt · Journal of Graph Theory · 2012
Abstract Tutte proved that every 3‐connected graph G on more than 4 vertices contains a contractible edge. We strengthen this result by showing that every depth‐first‐search tree of G contains a contractible edge. Moreover, we show that every spanning tree of G contains a contractible edge if G is 3‐regular or if G does not contain two disjoint pairs of adjacent degree‐3 vertices.