Hostname: page-component-74656f9884-8rzl6 Total loading time: 0 Render date: 2026-11-06T01:23:21.216Z Has data issue: false hasContentIssue false

Triangle Density and Contractibility

Published online by Cambridge University Press:  15 February 2005

MATTHIAS KRIESELL
Affiliation:
Instititut für Mathematik (A), Universität Hannover, Welfengarten 1, D-30167 Hannover, Germany (e-mail: kriesell@math.uni-hannover.de)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Paper
Copyright
© 2005 Cambridge University Press