Triangle-Free 2-Matchings Revisited

A \emph{2-matching} in an undirected graph $G=(VG,EG)$ is a function $f \colon EG \to \set{0,1,2}$suchthatforeachnode$v \in VG$thesumofvalues$f(e)$onalledges$e$incidentto$v$doesnotexceed2.The\mathit{\text{size}}of$f$isthesum$\sum_e f(e)$\mathrm{.}If$\set{e \in EG \mid f(e) \ne 0}$ contains no triangles then $f$ is called \emph{triangle-free}. Cornu'ejols and Pulleyblank devised a combinatorial $O(mn)$-algorithm that finds a triangle free 2-matching of maximum size (hereinafter $n:=\text{abs}VG$, $m:=\text{abs}EG$) and also established a min-max theorem. We claim that this approach is, in fact, superfluous by demonstrating how their results may be obtained directly from the Edmonds–Gallai decomposition. Applying the algorithm of Micali and Vazirani we are able to find a maximum triangle-free 2-matching in $O(m\sqrt{n})$-time. Also we give a short self-contained algorithmic proof of the min-max theorem. Next, we consider the case of regular graphs. It is well-known that every regular graph admits a perfect 2-matching. One can easily strengthen this result and prove that every $d$-regular graph (for $d\ge 3$) contains a perfect triangle-free 2-matching. We give the following algorithms for finding a perfect triangle-free 2-matching in a $d$-regular graph: an O(n)-algorithm for $d=3$, an $O(m+n^{3\mathrm{/}2})$-algorithm for $d=2k$ ($k \ge 2$),andan$O(n^2)$-algorithmfor$d = 2k + 1$($k \ge 2$). We also prove that there exists a constant $c>1$ such that every 3-regular graph contains at least $c^n$ perfect triangle-free 2-matchings.