\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 Ermelinda DeLaVi\~na and Bill Waller}
%
%
\medskip
\noindent
%
%
{\bf Spanning Trees with Many Leaves and Average Distance}
%
%
\vskip 5mm
\noindent
%
%
%
%
In this paper we prove several new lower bounds on the maximum number
of leaves of a spanning tree of a graph related to its order,
independence number, local independence number, and the maximum order
of a bipartite subgraph.  These new lower bounds were conjectured by
the program Graffiti.pc, a variant of the program Graffiti. We use two
of these results to give two partial resolutions of conjecture 747 of
Graffiti (circa 1992), which states that the average distance of a
graph is not more than half the maximum order of an induced bipartite
subgraph. If correct, this conjecture would generalize conjecture
number 2 of Graffiti, which states that the average distance is not
more than the independence number. Conjecture number 2 was first
proved by F. Chung.  In particular, we show that the average distance
is less than half the maximum order of a bipartite subgraph, plus
one-half; we also show that if the local independence number is at
least five, then the average distance is less than half the maximum
order of a bipartite subgraph. In conclusion, we give some open
problems related to average distance or the maximum number of leaves
of a spanning tree.

\bye