<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf Stephan G. Wagner}
%
%
\medskip
\noindent
%
%
{\bf Almost All Trees have an Even Number of Independent Sets}
%
%
\vskip 5mm
\noindent
%
%
%
%
This paper is devoted to the proof of the surprising fact that almost
all trees have an even number of independent vertex subsets (in the
sense that the proportion of those trees with an odd number of
independent sets tends to $0$ as the number of vertices approaches
$\infty$) and to its generalisation to other moduli: for fixed $m$,
the probability that a randomly chosen tree on $n$ vertices has a
number of independent subsets that is divisible by $m$ tends to $1$ as
$n \to \infty$.



\bye
</pre></body></html>