Triangle Density and Contractibility
- 1 January 2005
- journal article
- research article
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 14 (1-2) , 133-146
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) \geq 1$, which was later improved by Mader to $t(G) \geq \frac{1}{3}|V(G)|$. Here we show $t(G) \geq \frac{2}{3}|V(G)|$ (which is best possible in general). Furthermore it is proved that, for $k \geq 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 \geq 4$ every $k$-connected graph $G$ admits two disjoint induced cycles $C_1,C_2$ such that $G-V(C_1)$ and $G-V(C_2)$ are $(k-3)$-connected.