Smallest regular and almost regular triangle-free graphs without perfect matchings

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 >= 2 is an integer, G a triangle-free (d, d + 1)-graph of order n without an odd component and n <= 4d, then we show in this paper that G contains a perfect matching. Using a new Turan 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.