How can a graph be built such that it has an even number of vertices, and every vertex has degree $k$, but there are no perfect matchings (assuming $k$ is an even number greater than 3). It should be impossible to disconnect this graph by removing less than $k-2$ edges.
The complete graph on $k+1$ vertices works except for the fact that $K_{k+1}$ contains an even number of vertices. By taking the empty subset $S=\emptyset$, then number of odd components in $G-S$ is $1$, and $1>0=|S|$, so by Tutte's theorem, $G$ has no perfect matching.
Another thing that works when $k$ is odd is to use a variant of the 3-regular graph without perfect matchings, but this fails when $k$ is even (since then the components contain an even number of vertices).
How can a graph without perfect matchings that statifies all the conditions in the first paragraph be constructed?
Is it possible that this question was not well formulated and that it is in fact impossible to find such a graph that satisifies the condition of $|V|$ being even?
Best Answer
Here is an example of a $4$-regular, $2$-edge-connected graph with $30$ vertices and no perfect matching, taken from this paper:
The proof that there is no perfect matching is straightforward, Tutte's theorem style: each of the middle vertices can be matched to only one of the outer components, and the other two are left to fend for themselves with an odd number of vertices.
This picture generalizes similarly to how you generalized the bridgeless cubic construction to a $k$-regular construction for odd $k$. In fact, the above graph is slightly more complex than it has to be, because it's planar, which you didn't ask for. The generalization can just have $k-2$ vertices in the center and $k$ petals, each with a single edge to each of the vertices in the center $(k-2)$ edges total.
Then, of course, you need the petals to be $(k-2)$-edge-connected, nearly-$k$-regular graphs (with $k-2$ vertices of degree $k-1$, the remainder of degree $k$) on an odd number of vertices, but that shouldn't be hard. For example, let a petal be made up of three vertex sets $A$, $B$, $C$ of size $k-2$, $k-1$, $2$, respectively: $2k-1$ vertices in total. Each vertex in $A$ is adjacent to each vertex in $B$ - and the vertices in $A$ will also be connected to the center. Each vertex in $B$ is also adjacent to each vertex in $C$, bringing their degree up to $k$; finally, the two vertices in $C$ are adjacent to each other.
The entire graph has $k(2k-1)+(k-2) = 2k^2-2$ vertices, which is an even number.