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.
