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.

Difficulty level: Easy task (using definitions and simple reasoning)
Proving or derivation task
Cs translation
Send comment on task by email