k-regular simple graph without 1-factor

Solution 1:

If $k$ is even, then $K_{k+1}$ is $k$ regular with $k+1$ (odd) vertices, and hence has no $1$-factor (as a perfect matching requires an even number of vertices).

If $k$ is odd, consider the following graph. Start at an initial vertex, then branch out in $k$ directions. From each of those new vertices, branch out $k-1$many times. For each collection of $k-1$ vertices, draw another $k-1$ vertices opposite it, and connect each vertex on one side with every vertex on the other. Lastly, since $k-1$ is even, in the opposite $k-1$ collection, pair up each vertex with one other vertex. Note that: the initial vertex has $k$neighbors, each ensuing vertex has $k$ neighbors. Every vertex in the first $k-1$ collection is connected to the one that preceeded it and $k-1$ other ones in the matching $k-1$ set, so has $k$ neighbors. Lastly, each vertex in the $k-1$ matching set is connected to every vertex in the initial $k-1$ set, and one more. Thus our graph is $k$ regular. However, if we delete the initial vertex, each component has $$(k-1) + (k-1) + 1 = 2k - 1$$ vertices, which is an odd number, and so we get $k$ odd components. By Tutte's theorem, this means that our graph could not have had a $1$-factor.

Here is an illustrative drawing in the $5$ case:

Solution 2:

It is possible to have a $k$-regular (simple) graph with no 1-factor for each $k \gt 1$ (obviously in the trivial case $k=1$ the graph itself is a 1-factor).

For $k$ even the complete graph on $k+1$ nodes is an example, since there are an odd number of nodes (and a 1-factor or perfect matching implies an even number of nodes).

Petersen showed that any 3-regular graph with no cut-edge has a 1-factor, a result that has been generalized and sharpened. However a 3-regular graph on 16 nodes (connected but not (vertex) 1-connected) is shown in Figure 7.3.1 of this book chapter, about 3/4ths of the way through.

A construction for $k$ odd that generalizes this (connected but not 1-connected) approach is described in a MathHelpForum post. A central vertex $v^*$ has $k$ copies of a certain odd-order (number of nodes) graph connected to it, say $G_1,\ldots,G_k$. In any perfect matching, some edge for $v^*$ must be chosen, its removal leaving some components with odd-order (in which a perfect matching becomes impossible).