Is there a problem that is easy for cubic graph but hard for graphs with maximum degree 3?

Cubic graphs are graphs where every vertex has degree 3. They have been extensively studied and I'm aware that several NP-hard problems remain NP-hard even restricted to subclasses of cubic graphs, but some others get easier. A superclass of cubic graphs is the class of graphs with maximum degree $\Delta \leq 3$.

Is there any problem that can be solve in polynomial time for cubic graphs but that is NP-hard for graphs with maximum degree $\Delta \leq 3$?

• Degenrate answer that shows there can be different complexities (though neither is NP-Hard): Finding $\delta$ is constant time on cubic graphs but linear on graphs with $\Delta \le 3$. :-) – William Macrae Nov 24 '12 at 18:09
• Good point. :-) – Vinicius dos Santos Nov 24 '12 at 19:56
• For bad choices of encodings it can even be $NP$-hard when $\Delta \le 3$, but it will be much more valuable to find a problem that doesn't rely on a poor encoding, and even better if that problem is a well-studied one. – William Macrae Nov 24 '12 at 20:24
• To expand on William's comment, here is an artificial problem. Given a graph $G$, does the degree sequence of $G$, interpreted as the encoding of an instance of 3-SAT, represent a satisfiable instance? (Assuming the encoding is such that the all-3 degree sequence represents a satisfying assignment for every $n$.) :-) – Neal Young Nov 24 '12 at 20:30
• @101011 Vertex cover (and MaxIS) are NP-complete even for cubic planar graphs (see GT1 and GT20 in Garey and Johnson). There is a paper that claim that the problem remains NP-complete even with the further restriction of 3-connectedness. – Cyriac Antony Jan 29 at 5:01

Here's a reasonably natural one: on an input $(G,k)$, determine whether $G$ has a connected regular subgraph with at least $k$ edges. For 3-regular graphs this is trivial, but if max degree is 3 and the input is connected, not a tree, and not regular, then the largest such subgraph is the longest cycle, so the problem is NP-complete.
• @Tyson, it only needs to be hard for one $k$ to be hard, right? E.g. take $k=n$. David, do you need to stipulate that the subgraph should be connected? (Otherwise, any cycle cover (not just a Hamiltonian cycle) will have $n$ edges, and determining the existence of a cycle cover is in $P$.) – Neal Young Nov 24 '12 at 22:14