A greedy algorithm for finding a large 2-matching on a random cubic graph

A 2-matching of a graph $G$ is a spanning subgraph with maximum degree two. The size of a 2-matching $U$ is the number of edges in $U$ and this is at least $n-\text{k}(U)$ where $n$ is the number of vertices of $G$ and $\text{k}$ denotes the number of components. In this paper, we analyze the performance of a greedy algorithm $\text{textsc}2greedy$ for finding a large 2-matching on a random 3-regular graph. We prove that with high probability, the algorithm outputs a 2-matching $U$ with $\text{k}(U)=\tilde{\mathrm{\Theta }}\text{of}{n}^{1\mathrm{/}5}$.