Smallest Regular and Almost Regular Triangle-Free Graphs without Perfect Matchings

Abstract

A graph \(G\) is regular if the degree of each vertex of \(G\) is d and almost regular or more precisely a \((d,d + 1)\)-graph, if the degree of each vertex of \(G\) is either \(d\) or \(d+1\). If \(d \geq 2\) is an integer, \(G\) a triangle-free \((d,d + 1)\)-graph of order n without an odd component and \(n \leq 4d\), then we show in this paper that \(G\) contains a perfect matching. Using a new Turdn type result, we present an analogue for triangle-free regular graphs. With respect to these results, we construct smallest connected, regular and almost regular triangle-free even order graphs without perfect matchings.