I want to determine the complexity of these two problems (with a given k):
1) Determine if the graph G has a cycle of length less or equal than k;
2) Determine if the graph G has a cycle of length equal or more than k.
For the first problem, I think it is NP-complete because it is NP (but why?) and because we can reduce the HAM-CYCLE problem to it (but how?)
I don't know what to say about the second problem. Can you help me solving this and can you help me telling me what is a good method to solve these kind of problems?