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\ge 2$ is an integer, $G$ a triangle-free $(d,d+1)$-graph of order n without an odd component and $n\le 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.