Complexity of finding if a degree bounded graph H is a subgraph of an unbounded graph G
If H is the cycle on |G| vertices (and is of maximum degree 2), then this is the Hamiltonian cycle problem. Seems like your problem is NP-hard.