Separating Matchings in Cubic Graphs

Abstract

We study separating matchings in graphs, that is, matchings whose removal increases the number of connected components, and focus on determining the maximum size of such a matching in a graph $G$, denoted by $\mathrm{mms}(G)$. We show that every subcubic graph admits a separating matching, except for exactly eight graphs, which allows us to focus on bounding $\mathrm{mms}(G)$ for cubic graphs. Our main results show that every cubic graph $G$ on $n$ vertices that admits a separating matching satisfies $\mathrm{mms}(G)\ge n/2-2$. For bipartite cubic graphs, assuming a conjecture of Funk, the problem reduces to a recursively defined class $\mathcal{F}$, for which we prove that $\mathrm{mms}(G)\ge n/2-1$, up to four exceptional graphs. In contrast, we show that every claw-free cubic graph satisfies $\mathrm{mms}(G)=n/2$. These results extend previous work on matching cuts and disconnected $2$-factors, and provide the first systematic study of maximum separating matchings.