# NP-Completeness of Certain Bounded Degree Graphs

I was studying time complexity when it comes to bounded degree graph problems and I was wondering if I can get help with the following two problems.

1) L = set of all (G, k) where G is a graph with maximum degree of at most 4 and contains an independent set of size at least k. Is L in polynomial time or NP-complete?

2) L = set of all (G, k) where G is a graph with max degree 100 containing a clique of at least size k. Is L in P or NP-complete?

Since both Independent Set and Clique are NP-Complete, my first instinct is to say that 1) and 2) are both NP-complete. However, due to the bounded degree restriction, that is likely not true. I am not quite sure what I should be reducing from. Since if I were to attempt to show they are in P, I would have to reduce from something in P and I don't know anything that are remotely similar except Clique and Ind. Set, but like I said, those are NP-complete. I would really appreciate any help I can get with those two proofs. Any proof or hint would be very welcome!

EDIT: Actually after some research it seems that Independent Set problems tend to be NP-Complete when it comes to bounded degree graphs while Clique can usually be found in P-time or even linear time. I am not sure about this case, but it's a start I suppose.

-
Hmm...this is very odd. I just so happened to come across the exact same problems on a final I took three days ago. Coincidence?! I THINK NOT. – user26840 Mar 13 '12 at 16:27

Hint for (2): Suppose that $G$ was a graph with maximum degree $1$. Generalize.