A proof of Haemers' toughness conjecture

Abstract

We prove that if $\Gamma$ is a connected graph with minimum degree $\delta$ and Laplacian eigenvalues $0={\mu }_1<{\mu }_2⩽\cdots ⩽{\mu }_n$, then the toughness of $\Gamma$ is bounded below by ${\mu }_2/({\mu }_n-\delta )$.

arXiv comment9 pages