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

Prove that every $$k$$-regular edge $$(k-1)$$-connected graph on even number of vertices has a perfect matching.

• #### Hint

Follow the same arguments as in the proof of the theorem that every cubic graph without bridges has a perfect matching.

• #### Solution

We verify Tutte’s condition. Let $$S \subset V (G)$$. Denote by $$C_o (G, S)$$ the number of odd components in the graph $$G-S$$. Due to the connectivity, at least $$k-1$$ edges are incident with each odd component.

If $$k$$ is odd, an odd number of halfedges will be created in the odd component. Thus, an odd number of edges must lead from each odd component. Since $$k-1$$ is even, it must lead out at least $$k$$ edges.

If $$k$$ is even, an even number of halfedges will be created in each component and therefore an even number of edges stem out. Since $$k-1$$ is odd, it must lead out at least $$k$$ edges.

A total of $$k \cdot C_o (G, S)$$ edges are incident with odd components. Since the given graph is $$k$$-regular, and $$S$$ has to cover all edges leaving from the odd components, the size of the set $$S$$ shall satisfy: $$k | S | \geq k \cdot C_o (G, S)$$. After cancelling $$k$$ we get Tutte’s condition.  