Contractible Edges and Triangles in k-Connected Graphs

AbstractIt is proved that if G is a k-connected graph which does not contain K−4, then G has an edge e or a triangle T such that the graph obtained from G by connecting e or by contracting T is still k-connected. By using this theorem, we prove some theorems which are generalizations of earlier work. In addition, we give a condition for a k-connected graph to have a k-contractible edge, which implies two theorems proved by C. Thomassen (1981, J. Graph Theory5, 351–354) and by the author (2001, Australas. J. Combin.24, 165–168), respectively