\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 Bhalchandra D. Thatte }
%
%
\medskip
\noindent
%
%
{\bf Kocay's Lemma, Whitney's Theorem, and some Polynomial Invariant Reconstruction Problems}
%
%
\vskip 5mm
\noindent
%
%
%
%
Given a graph $G$, an incidence matrix ${\cal N}(G)$
is defined on the set of distinct isomorphism
types of induced subgraphs of $G$. It is proved that
Ulam's conjecture is true if and only if the
${\cal N}$-matrix is a complete graph invariant.
Several invariants of a graph are then shown to
be reconstructible from its ${\cal N}$-matrix. The
invariants include the characteristic polynomial, the
rank polynomial, the number of spanning trees 
and the number of hamiltonian cycles in a graph.
These results are stronger than the original results of
Tutte in the sense that actual subgraphs are not used.
It is also proved that the characteristic polynomial of
a graph with minimum degree 1 can be computed from the
characteristic polynomials of all its induced proper subgraphs.
The ideas in Kocay's lemma play a crucial role in most proofs.
Kocay's lemma is used to prove Whitney's subgraph
expansion theorem in a simple manner. The reconstructibility
of the characteristic polynomial is then demonstrated
as a direct consequence of Whitney's theorem as formulated here.

\bye

.
