k-regular graph , minimum edges deduction set Suppose we have a $k$-regular-graph where $k $ is an even number. If we call $ S $ as the minimum-edges-deduction-set (minimum amount of edges we have to delete from G to make it incoherent) and how can we prove that $|S| $ is an even number? In other words, how can we prove that $S $ contains an even number of edges?

Consider expanding on the proof that a $k$-regular graph, for even $k$, cannot have a bridge (an edge cut of odd order). That's done by contradiction. Suppose such a bridge $uv$ exists, and consider the two component graphs of $G-uv$. Now all vertices of each component have even degree except for one ($u$ or $v$). This is a contradiction by the Handshaking Lemma.

What goes wrong below if you remove the odd number of edges in S? How are the vertex degrees in each component affected (shown in red)? It fails on the Handshaking Lemma, or more generally, on the degree sum formula. ![enter image description here](