Every DFS tree of a 3-connected graph contains a contractible edge

摘要

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.