Contractible Edges and Bowties in a \(k\)-Connected Graph

Abstract

Let \(G\) be a \(k\)-connected graph and let \(F\) be the simple graph obtained from \(G\) by removing the edge \(xy\) and identifying \(x\) and \(y\) in such a way that the resulting vertex is incident to all those edges (other than \(xy\)) which are originally incident to \(x\) or \(y\). We say that \(e\) is contractible if \(F\) is \(k\)-connected. A bowtie is the graph consisting of two triangles with exactly one vertex in common. We prove that if a \(k\)-connected graph \(G\) (\(k \geq 4\)) has no contractible edge, then there exists a bowtie in \(G\).