Contractible Cliques in k-Connected Graphs

摘要

Kawarabayashi proved that for any integer k≥4, every k-connected graph contains two triangles sharing an edge, or admits a k-contractible edge, or admits a k-contractible triangle. This implies Thomassen's result that every triangle-free k-connected graph contains a k-contractible edge. In this paper, we extend Kawarabayashi's technique and prove a more general result concerning k-contractible cliques.