<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt]{article}
\usepackage{latexsym}
\usepackage{amsmath}
%\usepackage{showkeys}
\pagestyle{myheadings} 
\markright{\sc the electronic journal of combinatorics \textbf{7} (2000), \#R57\hfill} 
\thispagestyle{empty} 

\newif\ifdraft
%\drafttrue
\newcommand{\mnote}[1]{\ifdraft\marginpar{\footnotesize\raggedright#1}\fi}
\draftfalse

\setlength{\textwidth}{6.2in}
\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}
\setlength{\topmargin}{0in}
\setlength{\textheight}{8.5in}
\newcommand{\stack}[2]{\genfrac{}{}{0pt}{}{#1}{#2}}
\newcommand{\gap}[1]{\mbox{\hspace{#1 in}}}
\def\bx{{\bf x}}
\def\by{{\bf y}}
\def\cE{{\cal E}}
\def\cT{{\cal T}}
\def\bX{{\bf X}}
\def\bY{{\bf Y}}
\def\Rset{{\bf R}}
\def\cG{{\cal G}}
\def\hT{\hat{T}}
\def\bD{\bar{D}}
\def\hc{\hat{c}}
\def\hD{\hat{\D}_{i,j}}
\def\ep{\epsilon}
\def\ind{{\rm ind}}
\def\hw{\hat{w}}
\def\bs{\sigma}
\def\A{{\cal A}}
\def\B{{\cal B}}
\def\C{{\cal C}}
\def\E{{\bf E}}
\def\F{\Phi}
\def\H{{\cal H}}
\def\Ex{{\bf E}}
\def\cS{{\cal S}}
\def\cP{{\cal P}}
\def\bn{\bar{n}}
\def\bv{\bar{\n}}
\def\a{\alpha}
\def\b{\beta}
\def\d{\delta}
\def\D{\Delta}
\def\e{\epsilon}
\def\f{\phi}
\def\g{\gamma}
\def\G{\Gamma}
\def\k{\kappa}
\def\la{\lambda}
\def\K{\Kappa}
\def\z{\zeta}
\def\th{\theta}
\def\TH{\Theta}
\def\l{\lambda}
\def\L{\Lambda}
\def\m{\mu}
\def\n{\nu}
\def\p{\pi}
\def\P{\Pi}
\def\r{\rho}
\def\R{\Rho}
\def\s{\sigma}
\def\S{\Sigma}
\def\t{\tau}
\def\om{\omega}
\def\OM{\Omega}
\def\bigmid{\rule[-3.5mm]{0.1mm}{9mm}}
\def\N{{\cal N}}
\def\Pr{\mbox{{\bf Pr}}}
\def\CG{{\cal G}}
\def\CA{{\cal A}}
\def\whps{{\bf whp }}
\def\whp{{\bf whp}}
\def\Prob{{\bf Pr}}
\def\he{\hat{\e}}

\newtheorem{lemma}{Lemma}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}

\newcommand{\limninf}{\mbox{$\lim_{n \rightarrow \infty}$}}
\newcommand{\proofstart}{{\bf Proof\hspace{2em}}}
\newcommand{\tset}{\mbox{$\cal T$}}
\newcommand{\proofend}{\hspace*{\fill}\mbox{$\Box$}}
\newcommand{\bfm}[1]{\mbox{\boldmath $#1$}}
\newcommand{\reals}{\mbox{\bfm{R}}}
\newcommand{\expect}{\mbox{\bf E}}
\newcommand{\Exp}{\mbox{\bf E}}
\newcommand{\card}[1]{\mbox{$|#1|$}}
\newcommand{\scaps}[1]{\mbox{\sc #1}}
\newcommand{\rdup}[1]{{\mbox{$ \lceil #1 \rceil $}}}
\newcommand{\rdown}[1]{\lfloor #1 \rfloor }
\newcommand{\rt}{\right}
\newcommand{\lt}{\left}


\newcommand{\re}{\mbox{\rm e}}
\newcommand{\setm}{\setminus}

\newenvironment{proof}{\noindent{\bf Proof\,}}{\hfill$\Box$}
\newtheorem{remark}{Remark}
\newtheorem{conjecture}{Conjecture}

\newcommand{\no}{\noindent}
%\newcommand{\proof}{\medskip   \noindent
%{\bf Proof} \hspace{.2in}}
\newcommand{\eop}{ \hfill $\Box$ \bigskip
}
\newcommand{\asn}{as $\: n \rightarrow \infty$}
\begin{document}
\title{On the number of perfect matchings and Hamilton cycles
in $\e$-regular non-bipartite graphs}
\author{Alan Frieze\thanks{Supported in part by NSF Grant CCR9818411\gap{3}
\small Mathematics Subject Classification (1991); primary 05C50, 05C70,
secondary 05C80}\\
Department of Mathematical Sciences\\Carnegie Mellon University\\
Pittsburgh PA15213, USA\\{\small\texttt{alan@random.math.cmu.edu}}\\ \\
Submitted July 4, 2000, Accepted November 19, 2000\\ \\ }

\date{}
\maketitle

\begin{abstract}
A graph $G=(V,E)$ on $n$ vertices is super $\e$-regular if (i) all vertices have 
degree in the
range $[(d-\e)n,(d+\e)n]$, $dn$ being the average degree, and (ii) for every pair
of disjoint sets $S,T\subseteq V,\,|S|,|T|\geq \e n$, $e(S,T)$ is in the range
$[(d-\e)|S||T|,(d+\e)|S||T|]$. We show that the number of perfect matchings lies 
in the range
$[((d-2\e)^\n\frac{n!}{\n!2^\n},(d+2\e)^\n\frac{n!}{\n!2^\n}]$, where $\n=\frac{n}{2}$, 
and the number of 
Hamilton cycles
lies in the range $[(d-2\e)^nn!,(d+2\e)^nn!]$. 
\end{abstract}
\section{Introduction}
Let $G=(V,E)$ be a graph with $|V|=n$. Let $0&lt;d&lt;1$ and $\e&gt;0$ be constants
(independent of $n$) where $\e$ is assumed to be small compared with $d$.
We assume that the {\em density} of $G$ is $d$ i.e. $|E|/\binom{n}{2}=d$.
Suppose that the following two conditions hold:
\begin{itemize}
\item If $d_G$ denotes vertex degree in $G$ then
\begin{equation}\label{eq1}
(d-\e)n\leq d_G(v)\leq (d+\e)n \qquad\qquad\mbox{for all }v\in V.
\end{equation}
\item If for $S,T\subseteq V,\,S\cap T=\emptyset$ we let $e(S,T)$
denote the number of edges of $G$ with one end in $S$ and the other in $T$
and $d(S,T)=\frac{e(S,T)}{|S|\,|T|}$ then
\begin{equation}\label{eq2}
|d(S,T)-d|\leq \e\mbox{ for all }S,T\subseteq V,\,S\cap T=\emptyset,\,
|S|,|T|\geq \e n.
\end{equation}
\end{itemize}
A graph satisfying (\ref{eq1}),(\ref{eq2}) 
said to be {\em super $\e$-regular}. We assume
that $n=2\n$ is even. Let $m(G)$ denote the number of perfect matchings
in $G$ and let $h(G)$ denote the number of Hamilton cycles in $G$.
In this paper we prove 
\begin{theorem}\label{th1}
If $\e$ is sufficiently small and $n$ is sufficiently large then
\begin{description}
\item[(a)]
$$(d-2\e)^\n\frac{n!}{\n!2^\n}\leq m(G)\leq 
(d+2\e)^\n\frac{n!}{\n!2^\n}.$$
\item[(b)]
$$(d-2\e)^nn!\leq h(G)\leq (d+2\e)^nn!.$$
\end{description}
\end{theorem}
In both cases the bounds are ``close'' to the expected number of
in the random graph $G_{n,d}$.
The results here are strongly related to the result of  
Alon, R\"odl and Ruci\'nski \cite{ARR}. They considered bipartite 
graphs $H$ with vertex partition $A,B$ where $|A|=|B|=n$. Assuming
(\ref{eq1}) and (\ref{eq2}) for $S\subseteq A$ and $T\subseteq B$ they
proved 
\begin{theorem}\cite{ARR}\label{th2}
$$(d-2\e)^nn!\leq m(G)\leq (d+2\e)^nn!.$$
\end{theorem}
Michael Krivelevich has made some interesting observations on Theorem \ref{th1}:
First of all, part (b) of Theorem \ref{th1} improves 
Corollary 2.9 of Thomason \cite{thom} which estimates the
number of Hamilton cycles in a pseudo-random graph. 
Secondly, if $G$ is $dn$-regular and the second eigenvalue
of the adjacency matrix of $G$ is at most $\eta dn$ 
for small $\eta$, then $G$ is super $\e(\eta)$-regular (see
for example Chung \cite{chung} Theorem 5.1) and 
so our result holds for such graphs. 

We note that a similar result can be proven for the number of spanning trees in such a 
graph: if $t(G)$ denotes the 
number of spanning trees of $G$ then
\begin{equation}\label{trees}
(d-2\e)^{n-1}n^{n-2}\leq t(G)\leq (d+2\e)^{n-1}n^{n-2}.
\end{equation}
This follows from results of Alon \cite{Alon} and Kostochka \cite{Kostochka}.

We prove Theorem \ref{th1}(a) in the next section and Theorem \ref{th1}(b)
in Section \ref{sech}. For completeness, we also give a proof of (\ref{trees}) 
in Section \ref{secspan}.
\section{Perfect Matchings}\label{seca}
Let $A,B$, $|A|=|B|=\n$ be a partition of $V$. We re-express (\ref{eq2})
in terms of $\n$ i.e.
\begin{equation}\label{eq3}
|d(S,T)-d|\leq \e\mbox{ for all }S\subseteq A,\,T\subseteq B,\,
|S|,|T|\geq 2\e \n.
\end{equation}
Furthermore, if $A,B$ is a random partition and $H=H(A,B)$ is the 
bipartite sub-graph of $G$ induced by $A,B$ then with high probability 
$d_H(v)\in [(d-\e-o(1))\n,(d+\e+o(1))\n]$ for all $v\in V$. Thus the 
conditions of Theorem \ref{th2} are satisfied with $\n$ replacing
$n$ and $2\e$ replacing $\e$. It follows immediately that
\begin{equation}\label{eq4}
m(H)\geq (1-o(1))\binom{n}{\n}\times \n!(d-2\e)^\n\times \frac{1}{2^\n}
=(1-o(1))\frac{n!}{\n!2^\n}(d-2\e)^\n.
\end{equation}
The factor $\frac{1}{2^\n}$ accounts for the fact that each perfect matching
occurs in $2^\n$ different graphs $H$, assuming we consider the partition
$A,B$ distinct from $B,A$. There is slack in the calculation in \cite{ARR}
and this will absorb the $1-o(1)$ term and so (\ref{eq4}) proves the
lower bound in Theorem \ref{th1}.

For the upper bound we follow \cite{ARR} and use the Minc conjecture
\cite{Minc} proved by Bregman \cite{Breg}. For a partition $A,B$
and $v\in A$ let $d_B(v)$ denote the number of $G$-neighbours of $v$
in $B$. The Minc conjecture then states that
$$m(H)\leq \prod_{v\in A}(d_B(v))!^{1/d_B(v)}.$$
Thus
\begin{equation}\label{eq5}
m(G)\leq \frac{1}{2^\n}\sum_{A,B}\prod_{v\in A}(d_B(v))!^{1/d_B(v)}.
\end{equation}
For a fixed $A$, we let $A_1=\{v\in A:\;d_B(v)&gt;(d+\e)\n\}$. Property (\ref{eq1})
implies that $|A_1|\leq \e n$. Now since $(x!)^{1/x}$ increases with $x$, we see, after using
Stirling's approximation and (\ref{eq1}), that
\begin{multline*}
\prod_{v\in A}(d_B(v))!^{1/d_B(v)}\leq \left(\frac{d+\e}{e}\n\right)^{|A\setminus A_1|}
\left(\frac{d+\e}{e}n\right)^{|A_1|}\left(1+O\left(\frac{\ln n}{n}\right)\right)^\n\\
\leq \left(\frac{d+\e}{e}\n\right)^\n2^{\e n}n^{O(1)}.
\end{multline*}
Hence
$$m(G)\leq \frac{1}{2^\n}\binom{n}{\n}\left(\frac{d+\e}{e}\n\right)^\n2^{\e n}n^{O(1)}
\leq (d+2\e)^\n\frac{n!}{\n!2^\n}$$
completing the proof of part (a) of Theorem \ref{th1}.
\proofend
\section{Hamilton Cycles}\label{sech}
A Hamilton cycle is the union of two perfect matchings and so $h(G)\leq 
\frac{1}{2}m(G)^2$ and
the upper bound in part (b) of Theorem \ref{th1} follows from the upper bound in part (a).

The lower bound requires more work. For $1\leq k\leq \lfloor n/3\rfloor$, let 
$\Phi_k$ be the set of all 
2-factors in~$G$ containing exactly $k$~cycles, and let 
$\Phi=\cup_k\Phi_k$ be the set of all 2-factors.
Let $f_k=|\F_k|$ so that $f_1=h(G)$. If $M$ is a perfect matching of $G$, 
let $a_M$ denote the 
number of perfect matchings of $G$ that are disjoint from $M$. Since 
deleting $M$ only disturbs
$\e$-regularity marginally, we see by part (a) that $a_M\geq 
(d-2\e)^\n\frac{n!}{\n!2^\n}$. Thus
\begin{equation}\label{eq6}
A_G=\sum_{M\in G}a_M\geq \left((d-2\e)^\n\frac{n!}{\n!2^\n}\right)^2
\geq (d-2\e)^nn!\times \frac{1}{3n^{1/2}}.
\end{equation}
On the other hand, we have
\begin{equation}\label{eq7}
A_G\leq\sum_{k=1}^{\rdown{n/3}}2^kf_k.
\end{equation}
We will show by a relatively crude argument that where 
$k_1=\rdup{\frac{4}{(d-2\e)(d-\e)}}$
\begin{equation}\label{eq0}
\frac{f_{k+1}}{f_k}\leq n^3\qquad\qquad 1\leq k\leq k_1.
\end{equation}
We then use an idea from Dyer, Frieze and Jerrum \cite{DFJ}. In this paper they show that if
an $n$ vertex graph $G$ has minimum degree $\d(G)\geq (\frac{1}{2}+\a)n$ for a positive constant
$\a$, then a polynomial fraction of the 2-factors of $G$ are Hamilton cycles. We extend their argument
to $\e$-regular graphs.

Let $\beta=\frac{200}{(d-2\e)(d-\e)^2}$.
Let $k_0=\lfloor\beta\ln n\rfloor$, and for 
$1\leq k\leq n$, define $\g(k)=n^\beta k!(\beta\ln n)^{-k}$, and 
$$
\f(k)=\begin{cases}
\g(k),&amp;if\ k\leq k_0;\\
\g(k_0),&amp;otherwise.\\
\end{cases}
$$
\begin{lemma}
\label{fproperties}
Let $\f$ be the function defined above.  Then
\begin{enumerate}
\item $\f$ is non-increasing and satisfies
$$\min\{\f(k-1),\f(k-2)\}=\f(k-1)\geq (\beta\ln n)k^{-1}\f(k);$$
\item $\f(k)\geq1$, for all $k$.
\end{enumerate}
\end{lemma}
\proofstart
Observe that $\g$ is unimodal, and that $k_0$ is the value
of~$k$ minimizing $\g(k)$;  it follows that $\f$ is non-increasing.
When $k\leq k_0$, we have
$\f(k-1)=\g(k-1)=(\beta\ln n)k^{-1}\g(k)=(\beta\ln n)k^{-1}\f(k)$;
otherwise, $\f(k-1)=\g(k_0)=\f(k)\geq(\beta\ln n)k^{-1}\f(k)$.
In either case, the inequality in part~1 of the lemma holds.

Part~2 of the lemma follows from the chain of inequalities
$$\frac{1}{\f(k)}\leq\frac{1}{\g(k_0)}\leq\frac{(\beta\ln n)^{k_0}}{n^\beta k_0!}\leq 
n^{-\beta}\sum_{k=0}^\infty\frac{(\beta\ln n)^k}{k!}=n^{-\beta}\exp(\beta\ln n)=1.$$
\proofend

Define
$$\Psi =  \big\{(F,F'):F\in\Phi_k,F'\in\Phi_{k'},k'&lt;k,\mbox{ and }F\oplus F'\mbox{ is a 6-cycle}\big\},$$
where $\oplus$ denotes symmetric difference.  Observe that $\G=(\Phi,\Psi)$ is an 
acyclic directed graph;  let us agree to call its component parts 
{\it nodes\/} and {\it arcs\/} to avoid confusion with the vertices 
and edges of~$G$.  Observe also that if $(F,F')\in\Psi$ is an arc, 
then $F'$ can be obtained from~$F$ by deleting three edges and 
adding three others, and that this operation can decrease the number of 
cycles by at most two.  Thus every arc $(F,F')\in\Psi$ is directed 
from a node~$F$ in some~$\Phi_k$ to a node~$F'$ in~$\Phi_{k-1}$  
or~$\Phi_{k-2}$.

Our proof strategy is to define a positive weight function $w$ on 
the arc set~$\Psi$ such that the total weight of arcs leaving
each node (2-factor) $F\in\Phi_{\geq k_1}$ is significantly greater
than the total weight of arcs entering~$F$. We will show below that 
\begin{align}
\sum_{F^+:(F,F^+)\in\Psi}w(F,F^+)&amp;\geq100\f(k)n^2\ln n\qquad&amp;F\in 
\F_k,k\geq k_1,\label{eq8}\\
\sum_{F^-:(F^-,F)\in\Psi}w(F^-,F)&amp;\leq9\f(k)n^2H_n\qquad&amp;F\in \F_k,k\geq 1,\label{eq9}
\end{align}
where $H_n=\sum_{i=1}^ni^{-1}\leq\ln n+1$ is the $n$th harmonic 
number.

Now let
$$W_{k,l}=\sum_{\stack{F\in \F_k,F'\in \F_l}{(F,F')\in \Psi}}w(F,F').$$
Then (\ref{eq8}) and (\ref{eq9}) imply that for $k\geq k_1$,
\begin{eqnarray}
W_{k+2,k}+W_{k+1,k}&amp;\leq&amp;9f_k\f(k)n^2H_n\label{eq10}\\
W_{k,k-1}+W_{k,k-2}&amp;\geq&amp;100f_{k}\f(k)n^2\ln n.\label{eq11}
\end{eqnarray}
Now (\ref{eq11}) implies that either

(i) $W_{k,k-1}\geq 50f_{k}\f(k)n^2\ln n$ so that from (\ref{eq10})(k-1) we have
$$\frac{f_{k-1}}{f_{k}}\geq 5\frac{\f(k)}{\f(k-1)}$$
or

(ii) $W_{k,k-2}\geq 50f_{k}\f(k)n^2\ln n$ so that from (\ref{eq10})(k-2) we have
$$\frac{f_{k-2}}{f_{k}}\geq 5\frac{\f(k)}{\f(k-2)}$$
It follows that if $k\geq k_0+2$ then
$$f_k\leq 5^{-(k-k_0)/2}\max\{f_{k_0+1},f_{k_0}\}.$$
Then from (\ref{eq7}) we see that
\begin{equation}\label{eq12}
A_G\leq \frac{\sqrt{5}}{\sqrt{5}-2}\sum_{k=1}^{k_0+1}2^kf_k\leq  
\frac{\sqrt{5}}{\sqrt{5}-2}2^{k_0+1}\sum_{k=1}^{k_0+1}f_k.
\end{equation}
Furthermore, since $F\in \F_k,k&gt;k_1$ implies that 
$$\sum_{F^+:(F,F^+)\in\Psi}w(F,F^+)-\sum_{F^-:(F^-,F)\in\Psi}w(F^-,F)\geq 1$$
the total weight of arcs entering~$\Phi_{k_1}$ is an upper bound on
the number of 2-factors in $G$ with more than $k_1$ cycles and 
the maximum total weight of arcs entering a single node in~$\Phi_{k_1}$
is an upper bound on the ratio 
$\r=\frac{f_{k_1+1}+f_{k_1+2}+\cdots+f_{\rdown{n/3}}}{f_{k_1}}$.
Thus
$$\r\leq 9\f(1)n^2H_n=O(n^{2+\b}).$$
Combined with (\ref{eq12}) and (\ref{eq0}) we see that
\begin{equation}\label{}
A_G\leq n^{O(1)}f_1
\end{equation}
and the lower bound in Theorem \ref{th1}(b) follows from (\ref{eq6}), 
modulo taking advantage of
slack to absorb the $n^{O(1)}$ term.
\subsection{Proofs of (\ref{eq8}) and (\ref{eq9})}
The weight function $w:\Psi\to\Rset^+$
we employ is defined as follows.  For any 
arc $(F',F)$ with $F\in\Phi_k$:  
if the 2-factor~$F$ is obtained from~$F'$  
by coalescing two cycles of lengths $l_1$ and~$l_2$ into a single 
cycle of length $l_1+l_2$, then $w(F',F)=(l_1^{-1}+l_2^{-1})\f(k)$;
if $F$ results from coalescing three cycles of length 
$l_1$, $l_2$ and~$l_3$ into a single one of length $l_1+l_2+l_3$,
then $w(F',F)=(l_1^{-1}+l_2^{-1}+l_3^{-1})\f(k)$.

Let $F\in\Phi_k$ be a 2-factor with $k&gt;1$ cycles 
$C_1,C_2,\ldots,C_k$, of lengths 
$n_1,\allowbreak n_2,\ldots, n_k$.
We proceed to bound from below the total weight of arcs {\it leaving}~$F$.  
For this purpose imagine that the cycles 
$C_1,C_2,\ldots,C_k$ are 
oriented in some way, so that we can speak of each oriented edge
$(u,u')$ in some cycle~$C_i$ as being ``forward'' or
``backward''.  For each vertex $a$ we can then let $(a,\p(a))$ be the unique forward
edge containing $a$.
Since we are interested in obtaining a {\it lower\/} 
bound, it is enough to  
consider only arcs $(F,F^+)$ from~$F$ of a certain kind:
namely, those for which the 6-cycle $C=F\oplus F^+$
is of the form $C=(x,x',y,y',z,z')$, where $(x,x')\in F$ is a forward
cycle edge, $(y,y')\in F$ is a forward edge in a cycle distinct from the
first, and $(z,z')\in F$ is a backward cycle edge. The edge
$(z,z')$ may be in the same cycle as either $(x,x')$ or $(y,y')$,
or in a third cycle. 
Observe that $(x',y)$, $(y',z)$ and $(z',x)$ 
must necessarily be edges of~$F^+$.
It is routine to check that any cycle $C=(x,x',y,y',z,z')$
satisfying the above constraints does correspond to a valid arc 
from~$F$. The fact that $(z,z')$ is oriented in the opposite
sense to $(x,x')$ and $(y,y')$ plays a crucial role in ensuring that
the number of cycles decreases in the passage to~$F^+$ when 
only two cycles are involved. 
 
First, we estimate the number of cycles $C$ for which a fixed $(x,x')$
is contained in a particular cycle~$C_i$ of~$F$.
We say that $C$ is {\it rooted\/} at~$C_i$. 
Let $Z'$ be the neighbour set of $x$ in $G$ and $Z=\p(Z')$. Similarly,
let $Y'$ be the set of neighbours of $x'$ which do not belong to $C_i$ and let 
$Y=\p(Y')$. If $|Y'|\geq\e n$ then by $\e$-regularity
there are at least $(d-2\e)n$ vertices $z\in Z$ which have at
least $(d-\e)|Y'|\geq (d-\e)((d-\e)n-n_i)$ neighbours $y'$ in $Y'$.
Let $\d_i=1_{n_i\leq (d-2\e)n}$. We see that $\d_i=1$ implies  
$(x,x')$ is contained in at least $(d-2\e)(d-\e)((d-\e)n-n_i)n$ cycles.
Note also that $\sum_{i=1}^k\d_i\geq k-\frac{1}{d-2\e}$.

We can now bound the total weight of arcs leaving~$F$.  
Each arc $(F,F^+)$ defined by a cycle~$C$ rooted at~$C_i$
has weight at least $n_i^{-1}\min\{\f(k-1),\f(k-2)\}$, which, by 
Lemma~\ref{fproperties}, is bounded below by 
$(\beta\ln n)(kn_i)^{-1}\f(k)$.
Thus the total weight of arcs leaving $F$ is bounded as follows:
\begin{eqnarray}
\sum_{F^+:(F,F^+)\in\Psi}w(F,F^+)&amp;\geq&amp;
\sum_{i=1}^k(d-2\e)(d-\e)((d-\e)n-n_i)n\d_i
n_i\frac{(\beta\ln n)\f(k)}{kn_i}\label{initialsum}\\
&amp;\geq&amp;\b(d-2\e)(d-\e)\f(k)\left(d-\e-\frac{1}{k(d-2\e)}-\frac{1}{k}\right)
n^2\ln n\\
&amp;\geq&amp;\b(d-2\e)(d-\e)\f(k)\frac{d-\e}{2}n^2\ln n,\nonumber\\
&amp;\geq&amp;100\f(k)n^2\ln n\label{lowerbd}
\end{eqnarray}
where we have used the 
fact that $k\geq k_1$.
Note that the presence of a unique backward edge, namely $(z,z')$,
ensures that each cycle~$C$ has a distinguishable root, and hence that 
the arcs $(F,F^+)$ were not overcounted in summation~(\ref{initialsum}). This completes the proof of (\ref{eq8}). 

We now turn to the corresponding {\it upper\/} bound on the total weight of 
arcs $(F^-,F)\in\Psi$ {\it entering}~$F$.  
It is straightforward to verify that the cycle 
$C=(x,x',y,y',z,z')=F^-\oplus F$ must contain 
three edges~--- $(x,x')$, $(y,y')$ and ($z,z')$~--- 
from a single cycle~$C_i$ of~$F$,
the remaining edges coming from $F^-$. 
The labeling of vertices in~$C$ 
can be made canonical in the following way:  
assume an ordering on vertices in $V$, and assign label~$x$ to the 
smallest vertex.  The condition $(x,x')\in F$ uniquely identifies 
vertex~$x'$, and the labeling of the other vertices in the 
cycle~$C$ follows.

Removing the three edges $(x,x')$, $(y,y')$ and ($z,z')$
from~$C_i$ leaves a triple 
of simple paths of lengths (say) $a-1$, $b-1$ and $c-1$:  
these lengths correspond (respectively) to the 
segment containing $x$, the segment containing $x'$,  
and the remaining segment.
Going round the cycle $C_i$, starting at $x'$ and ending at~$x$,
the vertices $x,x',\allowbreak y,y',\allowbreak z,z'$ 
may appear in one of eight possible sequences:
\begin{center}
$  x', y', y, z', z, x;$\\
$  x', z, z', y, y', x;$\\
$  x', z, z', y', y, x;$\\
$  x', z', z, y, y', x;$\\
$  x', y', y, z, z', x;$\\
$  x', y, y', z', z, x;$\\
$  x', z', z, y', y, x;$\\
$  x', y, y', z, z', x.$
\end{center}
For a given triple of lengths $(a,b,c)$, 
each of the above sequences corresponds to at most 
$n_i$~possible choices for the edges $(x,x')$,
$(y,y')$ and $(z,z')$, yielding a maximum of~$8n_i$ in total.
To see this, observe that the edge $(x,x')$ may be chosen in $n_i$ 
ways (minimality of~$x$ fixes the orientation of the edge),
and that the choice of $(x,x')$ combined with the information
provided by the sequence completely determines the triple of edges.

The eight sequences divide into five possible cases,
as the first four sequences lead to equivalent 
outcomes (covered by case~1 below).
Taken in order, the five cases are:
\begin{enumerate}
\item For at most $4n_i$ of the choices for the edges $(x,x')$,
$(y,y')$ and $(z,z')$,
   $C_i\oplus C$ is a single cycle;  
\item for at most $n_i$ choices, $C_i\oplus C$ is 
   a pair of cycles of lengths $b$ and $a+c$;
\item for at most $n_i$ choices, $C_i\oplus C$ is 
   a pair of cycles of lengths $a$ and $b+c$;
\item for at most $n_i$ choices, $C_i\oplus C$ is 
   a pair of cycles of lengths $c$ and $a+b$;
\item for at most $n_i$ choices, $C_i\oplus C$ is 
   a triple of cycles of lengths $a$, $b$ and $c$.
\end{enumerate}
The first case does not yield an arc $(F^-,F)$, since 
the number of cycles does not decrease when passing 
from $F^-=F\oplus C$ to~$F$,
but the other four cases do have to be reckoned with.

The total weight of arcs entering~$F$ can be bounded above as follows:
\begin{eqnarray*}
\sum_{F^-:(F^-,F)\in\Psi}w(F^-,F)&amp;\leq&amp;\sum_{i=1}^k n_i\f(k)
\sum_{\stack{a,b,c\geq1}{a+b+c=n_i}}\left[\left(\frac{1}{a}+\frac{1}{b}+\frac{1}{ c}\right)
+\right.\nonumber \\
&amp;&amp;\left.\left(\frac{1}{a}+\frac{1}{b+c}\right) +\left(\frac{1}{b}+\frac{1}{a+c}\right)+ 
\left(\frac{1}{c}+\frac{1}{a+b}\right)\right]\nonumber\\
&amp;=&amp;\sum_{i=1}^k n_i \f(k)\sum_{\stack{a,b,c\geq1}{a+b+c=n_i}}
   \left[\frac{6}{ a}+\frac{3}{ b+c}\right]\nonumber\\
&amp;\leq&amp;\sum_{i=1}^k n_i\f(k)n\sum_{a=1}^{n_i-1}
   \left[\frac{6}{ a}+\frac{3}{ n_i-a}\right]\nonumber\\
&amp;\leq&amp;9\f(k)n^2H_n.
\end{eqnarray*}  
This completes the proof of (\ref{eq9}).
\subsection{Proof of (\ref{eq0})}
We show that if $F\in \F_k$ and $2\leq k\leq k_1$ then there is at least
one arc $(F,F')\in \Psi$. Since each $F'$ is the 
terminus of at most $n^3$ arcs, (\ref{eq0}) follows immediately.

Let $C_1$ be the largest cycle of $F$. Then $|C_1|\geq n/k_1\geq \frac{d^2}{5}n$.

{\bf Case 1}: $|C_1|\leq n-3\e n$.

$\e$-regularity implies that there are at most $\e n$ vertices $X$ which 
have fewer than $(d-\e)|C_1|$
neighbours in $C_1$. As there are at least $3\e n$ vertices not in $C_1$, there are vertices
$x_1,x_2\notin X$ which are neighbours on a cycle $C_2\neq C_1$. Let $A_i,i=1,2$ 
be the neighbour sets
of $x_i$ on $C_1$ and let $B_i=\p(A_i)$ for $i=1,2$. By assumption, 
$|B_i|\geq \frac{1}{5}d^2(d-\e)n$
for $i=1,2$ and so we can choose $B_i'\subseteq B_i,\,i=1,2$ such 
that $B_1'\cap B_2'=\emptyset$ and $|B_1'|=|B_2'|
\geq \frac{1}{6}d(d-\e)n$. $\e$-regularity implies that there is at 
least one edge joining $B_1',B_2'$.
Suppose this is the edge $(b_1,b_2)$. 
Then $x_1,\p^{-1}(b_1),b_1,b_2,\p^{-1}(b_2),x_2,x_1$ defines the 
requisite 6-cycle.

{\bf Case 2}: $|C_1|&gt; n-3\e n$.

Just take any two vertices which are neighbours on a cycle other than 
$C_1$. Each has at least $(d-4\e)n$
neighbours in $C_1$ and we can argue the existence of a 6-cycle as in the previous case.
\proofend

{\bf Remark:} The proof shows that the number of Hamilton cycles is within a polynomial
factor of the number of two factors of $G$. Therefore one can generate a (near) random
Hamilton cycle of $G$ by generating (near) random 2-factors of $G$ until a Hamilton
cycle is produced. By doing this sufficiently many times we expect to obtain a good
approximation to the ratio of Hamilton cycles to 2-factors. Since the number of 2-factors
of $G$ can be efficiently
approximated to within arbitrary accuracy (Jerrum, Sinclair and Vigoda
\cite{JSV}) we see that we can efficiently 
estimate the number of Hamilton cycles of $G$ to within
arbitrary accuracy. Formally, there is a Fully Polynomial Time Randomised Approximation 
Scheme for estimating the number of Hamilton cycles in an super $\e$-regular graph.
It is of course assume that $d&gt;0$ is constant and $\e&lt;d$. This same argument is
used in \cite{DFJ}.
\section{Spanning Trees}\label{secspan}
For the lower bound let $\Omega=\{f:\;V\to V:\;(v,f(v))\in E,\text{for all\ }v\in V\}$ 
be the set of
functions defined by each $v\in V$ choosing a neighbour $f(v)$. Clearly
\begin{equation}\label{t-1}
|\Omega|=\prod_{v\in V}d_G(v)\geq (d-\e)^nn^n.
\end{equation}
Each $f\in\Omega$ defines a digraph $D_f=(V,A_f)$, $A_f=\{(v,f(v):\;v\in V\}$.
A weak component of $D_f$ consists of a cycle $C$ with a rooted forest whose 
roots are in $C$.
Suppose that $D_f$ has $k_f$ weak components. We obtain a spanning tree of 
$G$ by (i) deleting
the lexicographically first edge of each cycle of $D_f$ and then 
(ignoring orientation) extending
the $k_f$ components to a spanning tree. We claim that if $\a=4/\sqrt{d-\e}$ and
$$\OM_1=\{f\in \OM:\;k_f\leq \a\sqrt{n}\}$$
then
\begin{equation}\label{t1}
|\OM_1|\geq |\OM|/2.
\end{equation}
Assume that (\ref{t1}) holds. Each spanning tree is obtained by 
deleting $k_f$ edges of a $D_f$ and then adding
$k_f-1$ edges. It follows that each spanning tree can be obtained 
in at most $\binom{N}{\a\sqrt{n}}^2,\,
N=\binom{n}{2}$ ways from a member of $\OM_1$. Thus
$$t(G)\geq {\textstyle \frac{1}{2}}n^{-4\a\sqrt{n}}(d-\e)^nn^n$$
and the lower bound in (\ref{trees}) follows.

\parindent 0in
{\bf Proof of (\ref{t1})}\\
Let $f$ be chosen randomly from $\OM$ and write
$$k_f=\sum_{v\in V}\frac{1}{|K_v|}$$
where $K_v$ is the weak component containing $v$. 

We will argue that
\begin{equation}\label{t2}
\Pr(|K_v|\leq k)\leq \frac{k^2}{(d-\e)n}\qquad\qquad k\geq 1.
\end{equation}
Given (\ref{t2}) we have
\begin{eqnarray*}
\E(|K_v|^{-1})&amp;\leq&amp;\sum_{k=1}^{\sqrt{(d-\e)n}}
\frac{1}{k}(\Pr(|K_v|\leq k)-\Pr(|K_v|\leq k-1))+
\frac{1}{\sqrt{(d-\e)n}}\\
&amp;\leq&amp;\sum_{k=1}^{\sqrt{(d-\e)n}}\frac{\Pr(|K_v|\leq k)}{k(k+1)}+\frac{1}{\sqrt{(d-\e)n}}\\
&amp;\leq&amp;\sum_{k=1}^{\sqrt{(d-\e)n}}\frac{1}{(d-\e)n}+\frac{1}{\sqrt{(d-\e)n}}\\
&amp;=&amp;\frac{2}{\sqrt{(d-\e)n}}
\end{eqnarray*}
Thus
$$\E(k_f)\leq \frac{2\sqrt{n}}{\sqrt{d-\e}}$$
and (\ref{t1}) follows from the Markov inequality.

To verify (\ref{t2}), start with $v$ and follow $v,f(v),f^2(v),\ldots,$ until 
there is a repetition in the 
sequence. The probability of a repetition at the $i$th step is at most 
$\frac{i}{(d-\e)n}$, since there
are always at least $(d-\e)n$ random choices for $f^i(v)$. If there are no 
repetitions by step $k$
then $|K_v|&gt;k$. Thus
$$\Pr(|K_v|\leq k)\leq \sum_{i=1}^k\frac{i}{(d-\e)n}$$
and (\ref{t2}) follows.
\proofend

For the upper bound in (\ref{trees}) 
let $\OM^*=\{f:\;V\to V:\;(v,f(v))\in E\text{\ or\ }f(v)=
v\text{\ for all\ }v\in V\}$.
Then 
$$t(G)\leq |\OM^*|\leq ((d+\e)n+1)^n\leq (d+2\e)^{n-1}n^{n-2}.$$
To see this consider the following injective map from the spanning trees of $G$ 
into $\OM^*$: orient
each edge of tree $T$ towards vertex 1 and then put $f(1)=1$. 

{\bf Acknowledgement} We thank Michael Krivelevich for his earlier 
comments and for pointing out the 
simple proof of the upper bound in (\ref{trees}).
\begin{thebibliography}{99}
\bibitem{Alon} N. Alon, {\em The number of spanning trees in regular
graphs}, Random Structures and Algorithms 1 (1990) 175--182.
\bibitem{ARR} N. Alon, V. R\"odl and A. Ruci\'nski,
{\em Perfect matchings in $\e$-regular graphs}, The Electronic
Journal of Combinatorics 5 (1998) \#R13.
\bibitem{Breg} L. M. Bregman, {\em Some properties of non-negative
matrices and their permanents}, Soviet Mathematics Doklady 14 (1973)
945--949.
\bibitem{chung} F. R. K. Chung, Spectral Graph Theory, CBMS monograph no. 92, 
American Mathematical
Society 1997.
\bibitem{DFJ} M. E. Dyer, A. M. Frieze and M. R. Jerrum, {\em  Approximately 
counting Hamilton cycles in dense graphs},
SIAM Journal on Computing 27 (1998) 1262--1272.
\bibitem{JSV} M. R. Jerrum, A. Sinclair and E. Vigoda, 
{\em A polynomial-time approximation algorithm for the 
permanent of a matrix with non-negative entries}, to appear.
\bibitem{Kostochka} A. V. Kostochka, {\em The number of spanning trees
in graphs with given degree sequences}, Random Structures and
Algorithms 6 (1995) 269--274.
\bibitem{Minc} H. Minc, Non-negative matrices, Wiley, 1988.
\bibitem{thom} A. Thomason, {\em Pseudo-random graphs}, Proceedings of Random 
Graphs 85, Annals of
Discrete Mathematics 33, M. Karonski, Z. Palka, eds., North Holland (1985) 307--331.
\end{thebibliography}


\end{document}

</pre></body></html>