On the size of odd order graphs with no almost perfect matching.
Lutz Volkmann · 2004
A graph G is 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 and G a(d, d + 1)-graph with exactly one odd component and with no almost perfect matching, then we show in this paper that |V (G) | ≥4(d +1)+1and|V(G) | ≥4(d + 1) + 3 when d is odd. This result generalizes corresponding statements by C. Zhao (J. Combin. Math. Combin. Comput. 9 (1991), 195–198) and W.D. Wallis (Ars Combin. 11 (1981), 295–300) on the size of even order graphs without a perfect matching. Examples will show that the given bounds are best possible, and some related results are also presented.