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\ge 4$) has no contractible edge, then there exists a bowtie in $G$.