Cubic Subgraph

Input

Graph G=(V,E)G = (V, E).

Question

Is there a nonempty subset E′⊆EE' \subseteq E such that in the graph G′=(V′,E′)G' = (V', E') every vertex has either degree 3 or degree 0?

Classes

Proofs

NP-complete

Transformation from [problem:graph-3-colorability].

Reducible from