## k-regular edge k-connected graph

### Task number: 4051

Prove that every $$k$$-regular edge $$k$$-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$$ edges are incident with each odd component.

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.

Note also that for odd $$k$$ the graph has an even number of vertices according to the principle of evenness, but for even this condition must be guaranteed separately.