We describe fully polynomial randomized approximation schemes for the
problems of determining the number of Hamilton paths and cycles in an
n-vertex graph with minimum degree (1/2 + alpha)n, for any fixed alpha
> 0. We show that the exact counting problems are #P-complete. We als
o describe fully polynomial randomized approximation schemes for count
ing paths and cycles of all sizes in such graphs.