The Smallest Regular Graphs Which Are Not \(1\)-Extendable

Lutz Volkmann1
1 Lehrstuhl II fiir Mathematik, RWTH Aachen University, 52056 Aachen, Germany

Abstract

A graph \(G\) is \(\)-extendable if every edge is contained in a perfect matching of \(G\). In this note, we prove the following theorem. Let \(d \geq 3\) be an integer, and let \(G\) be a \(d\)-regular graph of order \(n\) without odd components. If \(G\) is not \(1\)-extendable, then \(n \geq 2d + 4\). Examples will show that the given bound is best possible.