## k-regular edge (k-2)-connected graph

For each $$k \ge 3$$, find a $$k$$-regular edge $$(k-2)$$-connected graph on an even number of vertices that does not have a perfect matching.

• #### Hint

Construct an odd component and a set $$S$$ so that it can be seen that the resulting graph violates Tutte’s condition.

• #### Solution

For even $$k$$ we create an odd component from $$K_{k + 1}$$ so that we select a matching on $$\frac{k-2}{2}$$ edges, and remove those edges. Let’s call this graph $$K’$$.

We take a total of $$k$$ copies of $$K’$$ and add to them $$k-2$$ new vertices forming the set $$S$$. We connect these parts so that each vertex of $$S$$ is adjacent to one vertex from each copy of $$K’$$ and that the resulting graph is $$k$$-regular. In other words, the edges between $$S$$ an4d each copy of $$K’$$ form a perfect matching between $$S$$ and the vertices of degree $$k-1$$ in $$K’$$.

After removing the set $$S$$ from the resulting graph $$G$$ we have $$| S + 2 |$$ odd components, and therefore $$G$$ violates Tutte condition and does not have a perfect matching.

It remains to show that if we remove any $$k-3$$ edges from $$G$$, the graph will remain connected. Each copy of $$K’$$ will have a vertex adjacent to the others, so it is connnected. From each vertex $$S$$ at least one edge leads to some copy of $$K’$$. According to Dirichlet’s principle, at least one vertex of $$S$$ is adjacent to all copies of $$K’$$, so the resulting graph is connected.

For odd $$k$$ we proceed in the same way, only the construction of $$K’$$ requires one extra step. As in the previous case we select from $$K_{k + 1}$$ a matching on $$\frac{k-3}{2}$$ edges, and remove those edges. Next, we choose another matching with $$\frac{k-1}{2}$$ edges. We subdivide each edge of this matching with one new one vertex. We merge these $$\frac{k-1}{2}$$ vertices into one, and obtain the $$(k-2)$$-nd, i.e. the last required vertex of degree $$k-1$$.

It remains to verify that the resulting graph $$K’$$ is sufficiently conneceted. By using Menger’s theorems, it can be shown that the addition of a single vertex, which results from the merge of vertices of subdivided edges, maintains the $$(k-2)$$-connnectedness.   