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. 1. Introduction Regular graphs have been extensively studied from a structural point of view (see e.g., [2]) but negligible research has been done on deciding whether a given graph contains, as a subgraph (not necessarily induced), a regular subgraph of some degree different from 3: the only case studied in the past is that where the regular subgraph should have degree 3 ( i.e., it should be cubic). The result that deciding whether a graph contains a cubic subgraph is NP-complete was attributed to Chvatal in [6], and was expanded upon in [7], where it was shown that the problem of deciding whether a planar graph of degree at most 7 has a cubic subgraph is NP-complete, and in [g], where it was shown that the problem of deciding whether a connected bipartite graph of degree at most 4 has a cubic subgraph is NP-complete. Surprisingly, no one has studied the problem REG(k) of deciding whether a graph has a regular subgraph of some given fixed degree
['Iain A. Stewart']
Finding regular subgraphs in both arbitrary and planar graphs