k-regular edge (k-1)-connected graph
Task number: 4052
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.
