Finding regular subgraphs in both arbitrary and planar graphs

Abstract

We show that the problems of deciding (i) whether an arbitrary graph has a k-regular subgraph, for some given k ⩾ 3, (ii) whether a planar graph has a quartic subgraph, and (iii) whether a planar graph has a quintic subgraph, are complete for NP via logspace reductions. There are no regular planar graphs of degree greater than 5.