Maximum cardinality 1-restricted simple 2-matchings (Q1010633)

Summary: A simple 2-matching in a graph is a subgraph all of whose nodes have degree 1 or 2. A simple 2-matching is called \(k\)-restricted if every connected component has \(>k\) edges. We consider the problem of finding a \(k\)-restricted simple 2-matching with a maximum number of edges, which is a relaxation of the problem of finding a Hamilton cycle in a graph. Our main result is a min-max theorem for the maximum number of edges in a 1-restricted simple 2-matching. We prove this result constructively by presenting a polynomial time algorithm for finding a 1-restricted simple 2-matching with a maximum number of edges.