Every DFS Tree of a 3‐Connected Graph Contains a Contractible Edge |
| |
| Authors: | Amr Elmasry Kurt Mehlhorn Jens M Schmidt |
| |
| Institution: | 1. COMPUTER SCIENCE DEPARTMENT, UNIVERSITY OF COPENHAGEN, , DENMARK;2. MPI FüR INFORMATIK, , 66123 SAARBRüCKEN, GERMANY;3. DEPARTMENT OF COMPUTER SCIENCE, , FU BERLIN, GERMANY |
| |
| 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. |
| |
| Keywords: | edges 3‐connected graph spanning tree DFS‐tree |
|
|
