Elmasry, Amr; Mehlhorn, Kurt; Schmidt, Jens M. Every DFS tree of a 3-connected graph contains a contractible edge. (English) Zbl 1259.05097 J. Graph Theory 72, No. 1-2, 112-121 (2013). Summary: 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. Cited in 3 Documents MSC: 05C40 Connectivity 05C05 Trees Keywords:edges; 3-connected graph; spanning tree; DFS-tree Software:LEDA PDFBibTeX XMLCite \textit{A. Elmasry} et al., J. Graph Theory 72, No. 1--2, 112--121 (2013; Zbl 1259.05097) Full Text: DOI References: [1] Ando, Contractible edges in 3-connected graphs, J Comb Theory Ser B 42 (1) pp 87– (1987) · Zbl 0611.05037 [2] Cormen, Introduction to Algorithms (2009) [3] Dean, Longest cycles in 3-connected graphs contain three contractible edges, J Graph Theory 12 (1) pp 17– (1989) · Zbl 0664.05031 [4] Elmasry, An O(n+m) certifying triconnectivity algorithm for Hamiltonian graphs, Algorithmica (2011) [5] Halin, Zur Theorie der n-fach zusammenhängenden Graphen, Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg 33 (3) pp 133– (1969) · Zbl 0172.25802 [6] Holton, Removable edges in 3-connected graphs, J Graph Theory 14 (4) pp 465– (1990) · Zbl 0729.05037 [7] Hopcroft, Dividing a graph into triconnected components, SIAM J Comput 2 (3) pp 135– (1973) · Zbl 0281.05111 [8] Kang, Removable edges of a spanning tree in 3-connected 3-regular graphs, in: Frontiers in Algorithmics pp 337– (2007) · Zbl 1214.05063 [9] Kratsch, Certifying algorithms for recognizing interval graphs and permutation graphs, SIAM J Comput 36 (2) pp 326– (2006) · Zbl 1113.68112 [10] Kriesell, A survey on contractible edges in graphs of a prescribed vertex connectivity, Graphs and Combinatorics 18 (1) pp 1– (2002) · Zbl 0997.05054 [11] Kriesell, On the number of contractible triples in 3-connected graphs, J Comb Theory Ser B 98 (1) pp 136– (2008) · Zbl 1127.05060 [12] Lucas, Récréations Mathématiques, Part 1 (1891) [13] Mader, Generalizations of critical connectivity of graphs, Discrete Math 72 pp 267– (1988) · Zbl 0664.05028 [14] McConnell, Certifying algorithms, Computer Science Review 5 (2) pp 119– (2011) · Zbl 1298.68289 [15] Mehlhorn, The LEDA Platform of Combinatorial and Geometric Computing (1999) · Zbl 0976.68156 [16] K. Mehlhorn P. Schweitzer Progress on certifying algorithms Proceedings of the 4th International Workshop on Frontiers in Algorithmics (FAW’10) 1 5 2010 [17] Miller, A new graph triconnectivity algorithm and its parallelization, Combinatorica 12 (1) pp 53– (1992) · Zbl 0753.05064 [18] Ota, The number of contractible edges in 3-connected graphs, Graphs and Combinatorics 4 (1) pp 333– (1988) · Zbl 0658.05047 [19] J. M. Schmidt Construction sequences and certifying 3-connectedness 27th International Symposium on Theoretical Aspects of Computer Science (STACS’10) 633 644 2010 [20] J. M. Schmidt Structure and Constructions of 3-Connected Graphs PhD thesis, Freie Universität Berlin, Germany 2011 [21] Tarjan, Depth-first search and linear graph algorithms, SIAM J Comput 1 (2) pp 146– (1972) · Zbl 0251.05107 [22] Tutte, A theory of 3-connected graphs, Indag Math 23 pp 441– (1961) · Zbl 0101.40903 [23] Veldman, Non k-critical vertices in graphs, Discrete Math 44 pp 105– (1983) · Zbl 0542.05043 [24] Vo, Finding triconnected components of graphs, Linear and Multilinear Algebra 13 pp 143– (1983) · Zbl 0514.05039 [25] Vo, Segment graphs, depth-first cycle bases, 3-connectivity, and planarity of graphs, Linear and Multilinear Algebra 13 pp 119– (1983) · Zbl 0514.05029 [26] Wu, Contractible elements in graphs and matroids, Combinatorics, Probability and Computing 12 (4) pp 457– (2003) · Zbl 1045.05027 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.