Triangle density and contractibility

Abstract

Let G be a noncomplete k -connected graph such that the graphs obtained from contracting any edge in G are not k-connected, and let t(G) denote the number of triangles in G. Thomassen proved t(G) ≥ 1, which was later improved by Mader to t(G) ≥ 1/3|V(G)|. Here we show t(G) ≥ 2/3|V(G)| (which is best possible in general). Furthermore it is proved that, for k ≥ 4, a k-connected graph without two disjoint triangles must contain an edge not contained in a triangle whose contraction yields a k-connected graph. As an application, for k ≥ 4 every k-connected graph G admits two disjoint induced cycles C1, C2 such that G - V(C1) and G - V(C2) are (k - 3)-connected.