  In this paper we study the problem of finding a maximum induced d-degenerate
subgraph in a given n-vertex graph from the point of view of exact algorithms.
We show that for any fixed d one can find a maximum induced d-degenerate
subgraph in randomized (2-eps_d)^n n^O(1) time, for some constant eps_d>0
depending only on d. Moreover, our algorithm can be used to sample
inclusion-wise maximal induced d-degenerate subgraphs in such a manner that
every such subgraph is output with probability at least (2-eps_d)^-n; hence, we
prove that their number is bounded by (2-eps_d)^n.
