The Smallest Regular Graphs Which Are Not $1$-Extendable

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\ge 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\ge 2d+4$. Examples will show that the given bound is best possible.