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-\k(U)$ where n is the number of vertices of G and $\k$ denotes the number of components. In this paper, we analyze the performance of a greedy algorithm \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$\k(U) = \tilde{\Theta}\of{n^{1/5}}$.