Triangle-Free Graphs of Toughness Approaching Two Without a 2-Factor

Abstract

By work of Enomoto, Jackson, Katerinis, and Saito from 1985, every $2$-tough graph has a $2$-factor, and this toughness bound is best possible: for every $\varepsilon>0$, there exist $(2-\varepsilon)$-tough graphs with no $2$-factor. It is natural to ask whether the latter statement remains true for triangle-free graphs. Bauer, van den Heuvel, and Schmeichel conjectured this in 1996. In the same paper, they proposed an infinite family of triangle-free graphs with no $2$-factor whose toughness they believed approaches $2$, but the required toughness bound was not established. In this paper, we confirm their conjecture. For every even integer $q\ge 6$, we construct a triangle-free graph $G_q$ with no $2$-factor and with toughness \[ τ(G_q) =\frac{2q^2-q-2}{q^2+q} =2-\frac{3q+2}{q^2+q}. \] In particular, $τ(G_q)\to 2$ as $q\to\infty$, showing that the threshold $2$ for the existence of a $2$-factor remains best possible even within the class of triangle-free graphs.

Disclosure

“Gq − X). Thus every vertex cut X satisfies |X| ≥ τ c(Gq − X), proving that τ (Gq ) ≥ τ . Combining Claims 3.3 and 3.4 proves the equality τ (Gq ) = τ . Together with Claim 3.1 and 3.2, this proves Theorem 1.1. Declaration of Use of AI Tools During the preparation of this manuscript, the author used ChatGPT 5.6 Plus to assist with language editing, grammar, clarity, and formatting. The author reviewed and verified all AI-assisted edits and take full responsibility for the”

PDF page 8

Classification

Formatting or typesetting

Multiplier

1

Verified

2026-08-23T05:16:02.416878Z

Structural counts