I'd like to use Corollary 5 of a paper by [Hell & Kirkpatrick on graph packings](http://www.sciencedirect.com/science/article/pii/0012365X8490150X) to obtain an NP-hardness result. They want a 2-vertex-connected graph $F$ such that every matching in $F$ leaves at least 3 vertices unmatched. I would also like the graph to be $k$-regular for some $k$. I don't particularly care about the size of the graph or $k$, but smaller would be better.


[Petersen's theorem](http://en.wikipedia.org/wiki/Petersen%27s_theorem) implies that no such graph exists for $k =3$, but other theorems in this spirit that I've found in handbooks etc. don't seem to rule out the existence of such a graph for other $k$. I've searched through the collection of graphs from Mathematica's $\texttt{GraphData}$, but it didn't contain any examples satisfying these conditions.


Is anyone aware of reasons why such an $F$ might not exist, or else has ideas where to look for an example of one?


(I previously mentioned circulant graphs as possibilities, but they won't work because they are Hamiltonian.)



Are there 2-connected regular graphs whose maximum matching leaves 3 vertices uncovered?
Take an even number $r\ge 4$. Take $r$ copies of a 3-connected graph $G$ which has odd order and is regular of degree $r$. Add two new vertices $x$ and $y$. For each copy of $G$, remove one edge and join one of its former endpoints to $x$ and the other to $y$.


This gives a 2-connected $r$-regular graph whose maximum matchings miss at least $r-2$ vertices. This type of construction is pretty standard. The Edmonds–Gallai decomposition theorem tells it all.


