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.
Citation
Lutz Volkmann. The Smallest Regular Graphs Which Are Not \(1\)-Extendable[J], Ars Combinatoria, Volume 104. 179-184. .