  An undirected graph G is d-degenerate if every subgraph of G has a vertex of
degree at most d. By the classical theorem of Erd\H{o}s and Gallai from 1959,
every graph of degeneracy d>1 contains a cycle of length at least d+1. The
proof of Erd\H{o}s and Gallai is constructive and can be turned into a
polynomial time algorithm constructing a cycle of length at least d+1. But can
we decide in polynomial time whether a graph contains a cycle of length at
least d+2? An easy reduction from Hamiltonian Cycle provides a negative answer
to this question: deciding whether a graph has a cycle of length at least d+2
is NP-complete. Surprisingly, the complexity of the problem changes drastically
when the input graph is 2-connected. In this case we prove that deciding
whether G contains a cycle of length at least d+k can be done in time
2^{O(k)}|V(G)|^{O(1)}. In other words, deciding whether a 2-connected n-vertex
G contains a cycle of length at least d+log n can be done in polynomial time.
  Similar algorithmic results hold for long paths in graphs. We observe that
deciding whether a graph has a path of length at least d+1 is NP-complete.
However, we prove that if graph G is connected, then deciding whether G
contains a path of length at least d+k can be done in time 2^{O(k)}n^{O(1)}. We
complement these results by showing that the choice of degeneracy as the `above
guarantee parameterization' is optimal in the following sense: For any
\epsilon>0 it is NP-complete to decide whether a connected (2-connected) graph
of degeneracy d has a path (cycle) of length at least (1+\epsilon)d.
