% a plain TeX file for a 14 page document
\magnification=\magstep1
\baselineskip=15pt
\normalbaselineskip=15pt

\input ../inputs/paperB

\def\diff{\mathbin{\mkern-1.5mu\setminus\mkern-1.5mu}}% for \setminus
\def\pu{{\cal P}(u)}
\def\pv{{\cal P}(v)}
\def\puv{{\cal P}(u,v)}
\def\th{\theta}
\def\mtg{{\rm mult}(\th, G)}
\def\mt#1{{\rm mult}(\th, #1)}
\def\match{\mathop{\hbox{$\mu$}}\nolimits}
\def\mgx{\match(G,x)}
\def\mx#1{\match(#1,x)}

\authors={C. D. Godsil}
\runninghead={Algebraic Matching Theory}
\font\smcp=cmcsc8 
\headline={\ifnum\pageno>1%
	{\smcp the electronic journal of combinatorics 2 (1995),
	\#R8\hfill\folio} \fi}
\pagefoot={\hss}

\rewritexrffilefalse
\rewritexrffiletrue
\readxrffile

\null\vskip0.5cm
\centerline{\bf ALGEBRAIC MATCHING THEORY}
\vskip1.0cm
\centerline
{C. D. Godsil
\footnote{$^1$}{Support from grant OGP0009439 of the National
Sciences and Engineering Council of Canada is gratefully
acknowledged.}}
\vskip0.5cm
\centerline{Department of Combinatorics and Optimization}
\centerline{University of Waterloo}
\centerline{Waterloo, Ontario}
\centerline{Canada N2L 3G1}
\centerline{\tt chris@bilby.uwaterloo.ca}
\bigskip
\centerline{Submitted: July 6, 1994;\quad Accepted: April 11, 1995.}


\vskip1.0cm
\bigskip\noindent{\narrower
{\bf Abstract:}  The number of vertices missed by a maximum matching in
a graph $G$ is the multiplicity of zero as a root of the matchings
polynomial $\mgx$ of $G$, and hence many results in matching theory
can be expressed in terms of this multiplicity.  Thus, if $\mtg$ denotes
the multiplicity of $\th$ as a zero of $\mgx$, then Gallai's lemma
is equivalent to the assertion that if $\mt{G\diff u}<\mtg$ for
each vertex $u$ of $G$, then $\mtg=1$.

This paper extends a number of results in matching theory to results
concerning $\mtg$, where $\th$ is not necessarily zero.  If $P$ is a
path in $G$ then $G\diff P$ denotes the graph got by deleting the
vertices of $P$ from $G$.  We prove that $\mt{G\diff P}\ge\mtg-1$, and
we say $P$ is {\sl $\th$-essential}\/ when equality holds.  We show
that if, all paths in $G$ are $\th$-essential, then $\mtg=1$.  We define
$G$ to be {\sl $\th$-critical}\/ if all vertices in $G$ are
$\th$-essential and $\mtg=1$.  We prove that if $\mtg=k$ then there is
an induced subgraph $H$ with exactly $k$ $\th$-critical components,
and the vertices in $G\diff H$ are covered by $k$ disjoint paths.

\medskip\noindent
AMS Classification Numbers: 05C70, 05E99\par}


\section{intro}% 1
Introduction

A {\sl $k$-matching} in a graph $G$ is a matching with exactly $k$
edges and the number of $k$-matchings in $G$ is denoted by by
$p(G,k)$.  If $n=|V(G)|$ we define the matchings polynomial $\mgx$ by
$$
\mgx:=\sum_{k\ge0}(-1)^kp(G,k)x^{n-2k}.
$$
(Here $p(G,0)=1$.)  By way of example, the matchings polynomial of the
path on four vertices is $x^4-3x^2+1$.  The matchings polynomial is
related to the characteristic polynomial $\phi(G,x)$ of $G$, which is
defined to be the characteristic polynomial of the adjacency matrix of
$G$.  In particular $\phi(G,x)=\mgx$ if and only if $G$ is a forest
[\r{cg-ig}:~Corollary~4.2].  Also the matchings polynomial of any
connected graph is a factor of the characteristic polynomial of some
tree.  (For this, see \p{path-tree} below.)

Let $\mtg$ denote the multiplicity of $\th$ as a zero of $\mgx$.  If
$\th=0$ then $\mtg$ is the number of vertices in $G$ missed by a
maximum matching.  Consequently many classical results in the theory
of matchings provide information related to ${\rm mult}(0,G)$.  We
refer in particular to Gallai's lemma and the Edmonds-Gallai structure
theorem, which we now discuss briefly.

A vertex $u$ of $G$ is {\sl $\th$-essential}\/ if $\mt{G\diff u}<\mtg$.  
So a vertex is $0$-essential if and only if it is missed by some
maximum matching of $G$.  Gallai's lemma is the assertion that if $G$
is connected, $\th=0$ and every vertex is $\th$-essential then
$\mtg=1$.  (A more traditional expression of this result is given in
[\r{lv-pl}:~\S3.1].)  A vertex is {\sl $\th$-special}\/ if it is not
$\th$-essential but has a neighbour which is $\th$-essential.  The
Edmonds-Gallai structure in large part reduces to the assertion that
if $\th=0$ and $v$ is a $\th$-special vertex in $G$ then a vertex $u$
is $\th$-essential in $G$ and if and only if it is $\th$-essential in
$G\diff v$.  (For more information, see [\r{lv-pl}:~\S3.2].)  One aim
of the present paper is to investigate the extent to which these
results are true when $\th\ne0$.

There is a second source of motivation for our work.  Heilman and Lieb
proved that if $G$ has a Hamilton path then all zeros of $\mgx$ are
simple.  (This is an easy consequence of \p{path-del} below.)  Since
all known vertex-transitive graphs have Hamilton paths we are lead to
ask whether there is a vertex-transitive graph $G$ such that $\mgx$
has a multiple zero.  As we will see, it is easy to show that if $\th$
is a zero of $\mgx$ and $G$ is vertex-transitive then every vertex of
$G$ is $\th$-essential.  Hence, if we could prove Gallai's lemma for
general zeros of the matchings polynomial, we would have a negative
answer to this question.

\section{idents}% 2
Identities

The first result provides the basic properties of the matchings
polynomial $\mgx$.  We write $u\sim v$ to denote that the vertex $u$
is adjacent to the vertex $v$.  For the details see, for example,
[\r{cgbk}:~Theorem~1.1].

\result{recurs}% 2.1
Theorem.  The matchings polynomial satisfies the following identities:
\item{(a)} $\match(G\cup H,x)=\mgx\match(H,x)$,
\item{(b)} $\mgx=\match(G\diff e,x)-\match(G\diff uv,x)$
  if $e=\{u,v\}$ is an edge of $G$,
\item{(c)} $\mgx =x\match(G\diff u,x)
  -\sum_{i\sim u}\match(G\diff ui,x)$, if $u\in V(G)$,
\item{(d)} ${d\over dx}\mgx
  =\sum_{i\in V(G)}\match(G\diff i,x)$.\qed
  
Let $G$ be a graph with a vertex $u$.  By $\pu$ we denote the set of
paths in $G$ which start at $u$.  The {\sl path tree}\/ $T(G,u)$ of
$G$ relative to $u$ has $\pu$ as its vertex set, and two paths are
adjacent if one is a maximal proper subpath of the other.  Note that
each path in $\pu$ determines a path starting with $u$ in $T(G,u)$ and
with same length.  We will usually denote them by the same symbol.
The following result is taken from [\r{cgbk}:~Theorem~6.1.1].

\result{path-tree}% 2.2
Theorem.  Let $u$ be a vertex in the graph $G$ and let $T=T(G,u)$ be
the path tree of $G$ with respect to $u$.  Then
$$
{\match(G\diff u,x)\over\mgx}={\match(T\diff u,x)\over\match(T,x)} 
$$
and, if $G$ is connected, then $\mgx$ divides $\match(T,x)$.\qed

Because the matchings polynomial of a tree is equal to the
characteristic polynomial of its adjacency matrix, its zeros are real;
consequently \p{path-tree} implies that the zeros of the matchings
polynomial of $G$ are real, and also that they are interlaced by the
zeros of $\match(G\diff u,x)$, for any vertex $u$.  (By interlace, we
mean that, between any two zeros of $\mgx$, there is a zero of
$\match(G\diff u,x)$.  This implies in particular that the
multiplicity of a zero $\th$ in $\mgx$ and $\match(G\diff u,x)$ can
differ by at most one.)  For a more extensive discussion of these matters,
see [\r{cgbk}:~\S6.1].

We will need a strengthening of the first claim in \p{path-tree}.

\result{pt-cor}% 2.3
Corollary.  Let $u$ be a vertex in the graph $G$ and let $T=T(G,u)$ be
the path tree of $G$ with respect to $u$.  If $P\in\pu$ then 
$$
{\match(G\diff P,x)\over\mgx}={\match(T\diff P,x)\over\match(T,x)}.
$$

\proof
We proceed by induction on the number of vertices in $P$.  If $P$ has
only one vertex, we appeal to the theorem.  Suppose then that $P$ has
at least two vertices in it, and that $v$ is the end vertex of $P$
other than $u$.  Let $Q$ be the path $P\diff v$ and let $H$ denote
$G\diff Q$.  Then
$$
{\match(G\diff P,x)\over\mgx}
	={\match(G\diff P,x)\over\match(G\diff Q,x)}
		{\match(G\diff Q,x)\over\mgx}
	={\match(T(H,v)\diff v,x)\over\match(T(H,v),x)}
		{\match(T\diff Q,x)\over\match(T,x)},
$$
where the second equality follows by induction.  Now $T(H,v)$ is one
component of $T(G,u)\diff Q$, and if we delete the vertex $v$ from
this component from $T(G,u)\diff Q$, the graph that results is
$T(G,u)\diff P$.  Consequently
$$
{\match(T(H,v)\diff v,x)\over\match(T(H,v),x)}
	={\match(T\diff P,x)\over\match(T\diff Q,x)}.
$$
The results follows immediately from this.\qed

Let $\puv$ denote the set of paths in $G$ which start at $u$ and
finish at $v$.  The following result will be one of our main tools.
It is a special case of [\r{h-l}:~Theorem~6.3].

\result{HL}% 2.4
Lemma (Heilmann and Lieb).  Let $u$ and $v$ be vertices in the graph
$G$. Then
$$
\match(G\diff u,x)\match(G\diff v,x)
   -\mgx\match(G\diff uv,x)
 =\sum_{P\in\puv}\match(G\diff P,x)^2.\qed
$$

This lemma has a number of important consequences.  In
[\r{cg-rgp}:~Section~4] it is used to show that $\mtg$ is a lower
bound on the number of paths needed to cover the vertices of $G$, and
that the number of distinct zeros of $\mgx$ is an upper bound on the
length of a longest path.  For our immediate purposes, the following
will be the most useful.

\result{path-del}% 2.5
Corollary.  If $P$ is a path in the graph $G$ then $\match(G\diff
P,x)/\mgx$ has only simple poles.  In other words, for any zero $\th$
of $\mgx$ we have $$
\mt{G\diff P}\ge\mtg-1.
$$

\proof
Suppose $k=\mtg$.  Then, by interlacing, $\mt{G\diff u}\ge k-1$ for
any vertex $u$ of $G$ and $\mt{G\diff uv}\ge k-2$.  Hence the
multiplicity of $\th$ as a zero of 
$$
\match(G\diff u,x)\match(G\diff v,x)
   -\mgx\match(G\diff uv,x) 
$$ 
is at least $2k-2$.  It follows from \p{HL} that $\mt{G\diff P}\ge k-1$ 
for any path $P$ in $\puv$.\qed

\section{ess-vps}% 3
Essential Vertices and Paths

Let $\th$ be a zero of $\mgx$.  A path $P$ of $G$ is {\sl
$\th$-essential}\/ if $\mt{G\diff P}<\mtg$.  (We will often be
concerned with the case where $P$ is a single vertex.)  A vertex is
{\sl $\th$-special} if it is not $\th$-essential and is adjacent to an
$\th$-essential vertex.  A graph is {\sl $\th$-primitive}\/ if and
only if every vertex is $\th$-essential and it is 
{\sl $\th$-critical}\/ if it is $\th$-primitive and $\mtg=1$.  (When $\th$
is determined by the context we will often drop the prefix `$\th$-'
from these expressions.)  If $\th=0$ then a $\th$-critical graph is
the same thing as a factor-critical graph.

The next result implies that a vertex-transitive graph is $\th$-primitive 
for any zero $\th$ of its matchings polynomial.

\result{essvx}% 3.1
Lemma.  Any graph has at least one essential vertex.

\proof
Let $\th$ be a zero of $\mgx$ with multiplicity $k$.  Then $\th$ has 
multiplicity $k-1$ as a zero of $\match'(G,x)$.  Since
$$
\match'(G,x)=\sum_{u\in V(G)}\match(G\diff u,x)
$$
we see that if $\mt{G\diff u}\ge k$ for all vertices $u$ of $G$ then 
$\th$ must have multiplicity at least $k$ as a zero of $\match'(G,x)$.\qed

\result{essnbr}% 3.2
Lemma.  If $\th\ne0$ then any $\th$-essential vertex $u$ has a neighbour 
$v$ such that the path $uv$ is essential.

\proof
Assume $\th\ne0$ and let $u$ be a $\th$-essential vertex.  Since
$$
\mgx=x\mx{G\diff u}-\sum_{i\sim u}\mx{G\diff ui}
$$
we see that if $\mt{G\diff ui}\ge\mtg$ for all neighbours $i$ of $u$ 
then $\mt{G\diff u}\ge\mtg$.\qed

Note that the vertex $v$ is not essential in $G\diff u$.  However it
follows from the next lemma that the vertex $v$ in the above lemma
must be essential in $G$; accordingly if $\th\ne0$ then any essential
vertex must have an essential neighbour.

\result{no-essp}% 3.3
Lemma.  If $v$ is not an essential vertex of $G$ then no path with $v$
as an end-vertex is essential.

\proof
Assume $k=\mtg$.  If $v$ is not essential then $\mt{G\diff v}\ge k$
and so, for any vertex $u$ not equal to $v$, the multiplicity of $\th$
as a zero of 
$$
\match(G\diff u,x)\match(G\diff v,x)-\mgx\match(G\diff uv,x)
$$
is at least $2k-1$.  By \p{HL} we deduce that it is at least $2k$ and 
that $\mt{G\diff P}\ge k$ for all paths $P$ in $\pv$.\qed

We now need some more notation.  Suppose that $G$ is a graph and $\th$
is a zero of $\match(G,x)$ with positive multiplicity $k$.  A vertex
$u$ of $G$ is {\sl $\th$-positive}\/ if $\mt{G\diff u}=k+1$ and {\sl
$\th$-neutral}\/ if $\mt{G\diff u}=k$.  (The `negative' vertices will
still be referred to as essential.)  Note that, by interlacing,
$\mt{G\diff u}$ cannot be greater than $k+1$.

\result{posvs}% 3.4
Lemma.  Let $G$ be a graph and $u$ a vertex in $G$ which is not essential.  
Then $u$ is positive in $G$ if and only if some neighbour of it is 
essential in $G\diff u$.

\proof
From \p{recurs}(c) we have
$$
\mgx =x\match(G\diff u,x)
  -\sum_{i\sim u}\match(G\diff ui,x).\idno{vdel}
$$
If $\mt{G\diff u}=k+1$ and $\mt{G\diff ui}\ge k+1$ for all neighbours 
$i$ of $u$ then it follows that $\mtg\ge k+1$ and $u$ is not positive.

On the other hand, suppose $u$ is not essential in $G$ and $v$ is a
neighbour of $u$ which is essential in $G\diff u$.  From the previous
lemma we see that the path $uv$ is not essential and thus $\mt{G\diff
uv}\ge\mtg$.  As $v$ is essential in $G\diff u$ it follows that
$\mt{G\diff u}>\mtg$.\qed

We say that $S$ is an {\sl extremal}\/ subtree of the tree $T$ if $S$
is a component of $T\diff v$ for some vertex $v$ of $G$.

\result{extree}% 3.5
Lemma.  Let $S$ be an extremal subtree of $T$ that is
inclusion-minimal subject to the condition that $\mt{S}\ne0$, and let
$v$ be the vertex of $T$ such that $S$ is a component of $T\diff v$.
Then $v$ is $\th$-positive in $T$.

\proof
Let $u$ be the vertex of $S$ adjacent to $v$ and let $e$ be the edge
$\{u,v\}$.  Then $T\diff e$ has exactly two components, one of which
is $S$.  Denote the other by $R$.

By hypothesis $\mt{S'}=0$ for any component $S'$ of $S\diff u$,
therefore $\mt{S\diff u}=0$ by \p{recurs}(a) and so $u$ is essential
in $S$.  Since $S$ is a component of $T\diff v$ it follows that $u$ is
essential in $T\diff v$.  If we can show that $v$ is not essential
then $v$ must be positive in $T$, by the previous lemma.

Suppose $\mt{T}=m$.  By interlacing $\mt{T\diff u}\ge m-1$ and, as
$$
\mt{T\diff u}=\mt{R}+\mt{S\diff u}=\mt{R},
$$
we find that $\mt{R}\ge m-1$.  By parts (a) and (b) of \p{recurs} we have
$$
\mx T=\mx{R}\mx{S}-\mx{R\diff v}\mx{S\diff u}
$$
and so, since the multiplicity of $\th$ as a zero of $\mx{R}\mx{S}$ is 
at least $m$, we deduce that the multiplicity of $\th$ as a zero of
$\mx{R\diff v}\mx{S\diff u}$ is at least $m$.  Since $\mt{S\diff u}=0$, 
it follows that $\mt{R\diff v}\ge m$.  On the other hand
$$
\mt{T\diff v}=\mt{R\diff v}+\mt{S}=\mt{R\diff v}+1,
$$
therefore $\mt{T\diff v}\ge m+1$ and $v$ is positive in $T$.\qed

\result{Neu}% 3.6
Corollary (Neumaier).  Let $T$ be a tree and let $\th$ be a zero of $\mx{T}$.  
The following assertions are equivalent:
\item{(a)} $\mt{S}=0$ for all extremal subtrees of $T$,
\item{(b)} $T$ is $\th$-critical,
\item{(c)} $T$ is $\th$-primitive.

\proof
Since $T\diff v$ is a disjoint union of extremal subtrees for any
vertex $v$ in $T$, we see that if (a) holds then $\mt{T\diff v}=0$ for
any vertex $v$.  Hence $T$ is $\th$-critical and therefore it is also
$\th$-primitive.  If $T$ is $\th$-primitive then no vertex in $T$ is
$\th$-positive, whence \p{extree} implies that (a) holds.\qed

\p{Neu} combines Theorem~3.1 and Corollary~3.3 from [\r{neu}].  Note that
 the equivalence of (b) and (c) when $\th=0$ is Gallai's lemma for trees.

\result{simpz}% 3.7
Lemma.  Let $G$ be a connected graph.  If $u\in V(G)$ and all paths in
$G$ starting at $u$ are essential then $G$ is critical.

\proof
If all paths in $\pu$ are essential then \p{no-essp} implies that
all vertices in $G$ are essential.  Hence $G$ is primitive, and
it only remains for us to show that $\mtg=1$.

Let $T=T(G,u)$ be the path tree of $G$ relative to $u$.  From
\p{path-tree} we see that a path $P$ from $\pu$ is essential in $G$ if
and only if it is essential in $T$.  So our hypothesis implies that
all paths in $T$ which start at $u$ are essential, whence \p{no-essp}
yields that all vertices in $T$ are essential.  Hence $T$ is
$\th$-primitive and therefore, by \p{Neu}, $\th$ is a simple zero of
$\match(T,x)$.  Using \p{path-tree} again we deduce that $\mtg=1$.\qed

\result{ess-path}% 3.8
Lemma.  If $u$ and $v$ are essential vertices in $G$ and $v$ is not
essential in $G\diff u$ then there is a $\th$-essential path in $\puv$.

\proof
Assume $\mtg=k$.  Our hypotheses imply that $\mt{G\diff uv}\ge k-1$.
If no path in $\puv$ is essential then, by \p{HL}, the multiplicity
of $\th$ as a zero of
$$
\mx{G\diff u}\mx{G\diff v}-\mgx\mx{G\diff uv}
$$
is at least $2k$.  Since $\th$ has multiplicity $2k-1$ as a zero of
$\mgx\mx{G\diff uv}$ it must also have multiplicity at least $2k-1$ as
a zero of $\mx{G\diff u}\mx{G\diff v}$.  Hence $u$ and $v$ cannot both
be essential.\qed

If $u$ and $v$ are essential in $G$ then $v$ is essential in $G\diff
u$ if and only if $u$ is essential in $G\diff v$.  Thus the hypothesis
of \p{ess-path} is symmetric in $u$ and $v$, despite appearances.

\result{pths-vxs}% 3.9
Corollary.  Let $G$ be a tree, let $\th$ be a zero of $\mgx$ and let
$u$ be a vertex in $G$.  Then all paths in $\pu$ are essential if and
only if all vertices in $G$ are essential.

\proof
It follows from \p{no-essp} that if all paths in $\pu$ are essential
then all vertices in $G$ are essential.  Suppose conversely that all
vertices in $G$ are essential.  By \p{Neu} it follows that $\mtg=1$.
Hence the hypotheses of \p{ess-path} are satisfied by any two vertices
in $G$, and so any two vertices are joined by an essential path.
Since $G$ is a tree the path joining any two vertices is unique and
therefore all paths in $\pu$ are essential.\qed

\section{struct}% 4
Structure Theorems

We now apply the machinery we have developed in the previous section.

\result{deCaen}% 4.1
Lemma (De Caen [\r{ddc}]).  Let $u$ and $v$ be adjacent vertices in a 
bipartite graph.  If $u$ is $0$-essential then $v$ is $0$-special.

\proof
Suppose that $u$ and $v$ are $0$-essential neighbours in the bipartite 
graph $G$.  As $uv$ is a path, using \p{path-del} we find that
$$
{\rm mult}(0,G\diff uv)\ge{\rm mult}(0,G)-1={\rm mult}(0,G\diff u),
$$
and therefore $v$ is not essential in $G\diff u$.  It follows from 
\p{ess-path} that there is a $0$-essential path $P$ in $G$ joining 
$u$ to $v$.

We now show that $P$ must have even length.  From this it will follow
that $P$ together with the edge $uv$ forms an odd cycle, which is
impossible.  From the definition of the matchings polynomial we see
that ${\rm mult}(0, H)$ and $|V(H)|$ have the same parity for any
graph $H$.  As
$$ 
{\rm mult}(0,G\diff P)={\rm mult}(0,G)-1 
$$ 
we deduce that $|V(G)|$ and $|V(G\diff P)|$ have different parity and
therefore $P$ has even length.\qed

In the above proof we showed that a $0$-essential path in a graph must
have even length.  Consequently no edge, viewed as a path of length
one, can ever be $0$-essential.  It follows that $K_1$ is the only
connected graph such that all paths are $0$-essential.  In general any
graph which is minimal subject to its matchings polynomial having a
particular zero $\th$ will have the property that all its paths are
$\th$-essential.

\p{deCaen} is not hard to prove without reference to the matchings 
polynomial.  Note that it implies that in any bipartite graph there is
a vertex which is covered by every maximal matching, and consequently
that a bipartite graph with at least one edge cannot be $0$-primitive.
As noted by de Caen [\r{ddc}], this leads to a very simple inductive
proof of K\"onig's lemma.

Our next result is a partial analog to the Edmonds-Gallai structure
theorem. See, e.g., [\r{lv-pl}:~Chapter~3.2].
 
%\vbox{
\result{edgall}% 4.2
Theorem.  Let $\th$ be a zero of $\mgx$ with non-zero multiplicity $k$ and 
let $a$ be a positive vertex in $G$.  Then:
\item{(a)} if $u$ is essential in $G$ then it is essential in $G\diff a$;
\item{(b)} if $u$ is positive in $G$ then it is essential or positive in 
$G\diff a$;
\item{(c)} if $u$ is neutral in $G$ then it is essential or neutral in
$G\diff a$.
%\par}

\proof
If $\mt{G\diff u}=k-1$ and $\mt{G\diff a}=k+1$, it follows by
interlacing that $\mt{G\diff au}=k$.  Hence $u$ is essential in
$G\diff a$.  Now suppose that $u$ is positive in $G$.  If $\mt{G\diff
au}\ge k+1$ then $\th$ has multiplicity at least $2k+1$ as a zero of
$p(x)$ where
$$
p(x) := \mx{G\diff u}\mx{G\diff a}-\mgx\mx{G\diff au}.\idno{edg}
$$
By \p{HL}, the multiplicity of $\th$ as a zero of $p(x)$
must be even.  It follows that this multiplicity must be at least
$2k+2$ and hence that $\th$ has multiplicity at least $2k+2$ as a zero
of $\mgx\mx{G\diff au}$.  Therefore $\mt{G\diff au}\ge k+2$ and so, by
interlacing, $\mt{G\diff au}=k+2$ and $u$ is positive in $G\diff a$.
If $\mt{G\diff ua}=k+2$ and $u$ is neutral in $G$, then the
multiplicity of $\th$ as a zero of $p(x)$ is at least $2k+1$ and
therefore at least $2k+2$, but this implies that $\th$ is a zero of
$\mx{G\diff u}\mx{G\diff a}$ with multiplicity at least $2k+2$.  Thus
we conclude that $u$ is neutral or essential in $G\diff a$.\qed

We note that \p{edgall}(a) holds even if $a$ is only neutral.  If $a$
is neutral and $u$ is essential in $G$ but not in $G\diff a$ then
$\th$ has multiplicity at least $2k-1$ as a zero of \preveq/ and so
must have multiplicity at least $2k$ as a zero of $\mgx\mx{G\diff
au}$.  Hence its multiplicity as a zero of 
$\match(G\diff u,x)\match(G\diff a,x)$ is at least $2k$, 
which is impossible.

\medbreak
The following consequence of \p{edgall} and the previous remark was proved 
for trees by Neumaier. (See [\r{neu}:~Theorem~3.4(iii)].)

\result{neutree}% 4.3
Corollary.  Any special vertex is positive.

\proof
Suppose that $a$ is special in $G$, and that $u$ is a neighbour of $a$
which is essential in $G$.  By part (a) of the theorem and the remark
above, $u$ is essential in $G\diff a$ and therefore, by \p{posvs},
$a$ is positive in $G$.\qed

\p{simpz} implies that if $G$ is not $\th$-critical then it contains a
path, $P$ say, that is not essential.  If we delete $P$ from $G$ then
the multiplicity of $\th$ as a zero of $\mgx$ cannot decrease.  Hence
we may successively delete `inessential' paths from $G$, to obtain a
graph $H$ such that $\mt{H}\ge\mtg$ and all paths in $H$ are
essential.  If $k=\mt{H}$ then, by \p{simpz} again, $H$ contains
exactly $k$ critical components.  The following result is a sharpening
of this observation, since it implies that if $\mtg=k$ we may produce
a graph with $k$ critical components by deleting $k$ vertex disjoint
paths from $G$,

\result{critcomp}% 4.4
Lemma.  Let $G$ be a graph, let $\th$ be a zero of $\mgx$ and let $u$
be a $\th$-essential vertex of $G$.  Suppose that there is a path in
$\pu$ which is not $\th$-essential.  Then there is a path $P$ in $G$
starting at $u$ such that $\mt{G\diff P}=\mtg$ and some component $C$
of $G\diff P$ is critical.  All vertices of $C$ are essential in $G$.

\proof
Suppose that there are paths in $\pu$ which are not essential, choose
one of minimum length and call it $P$.  Let $v$ be the end-vertex of
$P$ other than $u$ and let $P'$ be the path $P\diff v$.  Then $P'$ is
essential, hence
$$
\mt{G\diff P'}=\mtg-1
$$
and, as $P$ is not essential,
$$
\mt{G\diff P}\ge \mtg.
$$
But we get $G\diff P$ from $G\diff P'$ by deleting the single vertex
$v$, therefore $\mt{G\diff P}=\mtg$ and $v$ is positive in $G\diff
P'$.  Consequently, by \p{posvs}, there is an essential vertex $u_1$
adjacent to $v$ in $(G\diff P')\diff v=G\diff P$.

We now prove by induction on the number of vertices that, if the
conditions of the lemma hold, then there is a path $P$ and a component
$C$ of $G\diff P$ as claimed and, further, there is a vertex $w$ in $C$
adjacent to the end-vertex of $P$ distinct from $u$ such that all paths
in $C$ that start at $w$ are essential in $C$.

Let $H$ denote $G\diff P$.  If all paths in $H$ starting at $u_1$ are
essential then, by \p{simpz}, the component $C$ of $H$
that contains $u_1$ is critical.  If $Q$ is a path in $C$ starting at
$u_1$ then $\mt{C\diff Q}<\mt{C}$; this implies that the path formed
by the concatenation of $P$ and $Q$ is essential in $G$ and hence, by
\p{no-essp}, that all vertices in $C$ are essential in $G$.

Thus we may suppose that there is a path in $H$ starting at $u_1$ that
is not essential.  Because $H$ has fewer vertices than $G$, we may
assume inductively that there is a path $Q$ in $H$ starting at
$u_1$ such that $\mt{H}=\mt{H\diff Q}$ and a critical component $C$ of
$H\diff Q$ that contains a neighbour $w$ of the end-vertex of $Q$ distinct
from $u_1$.  Further all the paths in $C$ that start at $w$ are essential.

Let $PQ$ denote the path formed by concatenating $P$ and $Q$.  Then
all claims of the lemma hold for $G$, $PQ$, $u$ and $C$.\qed

The two results which follow provide a strengthening of the
observation that the zeros of the matchings polynomial of a graph with
a Hamilton path are simple.

\result{gcd}% 4.5
Lemma.  Suppose that $u$ and $v$ are adjacent vertices in $G$ such
that $\mx{G\diff u}$ and $\mx{G\diff uv}$ have no common zero.  Then
$\mgx$ and $\mx{G\diff u}$ have no common zero, and therefore both
polynomials have have only simple zeros.

\proof
Assume by way of contradiction that $\th$ is a common zero of $\mgx$
and $\mx{G\diff u}$.  If $\mtg>1$ then by \p{path-del} we see that
$\th$ is a zero of $\mx{G\diff u}$ and $\mx{G\diff uv}$.  If
$\mt{G\diff u}>1$ then $\mt{G\diff uv}>0$, by interlacing.  Hence
$$
\mtg=\mt{G\diff u}=1
$$
and so $u$ is a neutral vertex in $G$.  It
follows from \p{posvs} that no neighbour of $u$ can be essential in
$G\diff u$ and consequently $\mt{G\diff uv}>0$.\qed

A simple induction argument on the length of $P$ yields the following.

\result{simples}% 4.7
Corollary.  Let $H$ be an induced subgraph of $G$ and suppose that there 
is a vertex $u$ in $H$ and a path $P$ in $G$ such that
$$
V(H)\cap V(P)=u,\qquad V(H)\cup V(P)=V(G).
$$
If $\match(H,x)$ and $\match(H\diff u,x)$ have no common zero then all 
zeros of $G$ are simple.\qed

Note that the path $P$ in this corollary does not have to be an induced path.  
One consequence of it is that if a graph has a Hamilton path then the zeros 
of its matchings polynomial are all simple.  However this result shows that 
there will be many other graphs with all zeros simple. 

\section{evs}% 5
Eigenvectors

Let $G$ be a graph with adjacency matrix $A=A(G)$.  We view an eigenvector 
$f$ of $A$ with eigenvalue $\th$ as a function on $V(G)$ such that
$$
\th f(u)=\sum_{i\sim u} f(i).
$$
We denote the characteristic polynomial of $G$ by $\phi(G,x)$.  (It is 
defined to be $\det(xI-A(G))$.)  We recall that for forests the 
characteristic and matchings polynomials are equal.  Our first result 
follows from the proof of Theorem~5.2 in [\r{cg-mw}].

\result{maxf}% 5.1
Lemma.  Let $\th$ be an eigenvalue of the graph $G$ and let $u$ be a vertex in $G$.  Then the maximum value of $f(u)^2$ as $f$ ranges over the 
eigenvectors of $G$ with eigenvalue $\th$ and norm one is equal to
$\phi(G\diff u,\th)/\phi'(G,\th)$.\qed

\result{neu-ess}% 5.2
Corollary (Neumaier [\r{neu}: Theorem~3.4]).  Let $T$ be a tree and
let $\th$ be a zero of its matchings polynomial.  Then a vertex $u$ is
essential if and only if there is an eigenvector $f$ of $T$ such that
$f(u)\ne0$.\qed

\result{tree-essv}% 5.3
Theorem.  Let $T$ be a tree, let $\th$ be a zero of $\mx{T}$ and let
$a$ be a vertex of $T$ which is not essential.  Then a vertex is
essential in $T\diff a$ if and only if it is essential in $T$.
Further, if $a$ is positive then it has an essential neighbour.

\proof
Let $W$ be the eigenspace of $T$ belonging to $\th$ and let $W_a$ be the 
corresponding eigenspace of $T\diff a$.  Then $W_a$ is the direct sum of 
the eigenspaces of the component of $T\diff a$ belonging to $\th$ and $W$ 
is the subspace formed by the vectors $f$ such that
$$
\sum_{i\sim a} f(i)=0.
$$
If $a$ is neutral then $W=W_a$ and so $T$ and $T\diff a$ have the same 
essential vertices.  If $a$ is positive then $W$ is a proper subspace of 
$W_a$, whence it follows that there are vectors in $W_a$ which are not 
zero on all neighbours of $a$.  For each vector in $W_a$ there is an 
eigenvector in $W$ with the same support on $T\diff a$.  Hence $a$ has an 
essential neighbour and any vertex which is essential in $T\diff a$ is 
also essential in $T$.\qed

\p{tree-essv} is a strengthening of a result of Neumaier 
[\r{neu}:~Corollary~3.5].  Suppose that $T$ is a tree with exactly $s$ 
special vertices and $\mt{T}=k$.  Then \p{tree-essv} together with \p{edgall} 
implies that we may successively delete the special vertices, obtaining a 
forest $F$ with no special vertices and $\mt{F}=k+s$.  Hence any component 
of $F$ is either $\th$-critical or does not have $\th$ as a zero of its 
matchings polynomial.  Therefore $F$ has exactly $k+s$ $\th$-critical 
components, and these components form an induced subgraph of $T$.

\section{qqq}%
Questions

Many problems remain.  Here are some.
\medbreak
\item{(1)}  Must a positive vertex be special when $\th\ne0$?  
(If $\th=0$ then all vertices which are not essential are positive.)
\item{(2)}  What can be said of the graphs where every pair of vertices are 
joined by at least one essential path?  (Or of the graphs with a vertex $u$
 such that all vertices can be joined to $u$ by an essential path?)
\item{(3)}  Must a $\th$-primitive graph be $\th$-critical?
\medbreak\noindent
It might be interesting to investigate the case $\th=1$ in depth.

\nonumsection
References

\ref{agt}
N. Biggs,
{\sl Algebraic Graph Theory}.
(Cambridge U.\ P., Cambridge) 1974.

\ref{ddc}
D. de Caen,
On a theorem of K\"onig on bipartite graphs,
{\sl J.\ Comb.\ Inf.\ System Sci.\ \bf13} (1988) 127.

\ref{cg-mw}
C. D. Godsil,
Matchings and walks in graphs,
{\sl J.\ Graph Theory, \bf 5}, (1981) 285--297.

\ref{cg-ig}
C. D. Godsil and I. Gutman,
On the theory of the matching polynomial,
{\sl J.\ Graph Theory, \bf 5} (1981), 137--144.

\ref{cg-rgp}
C. D. Godsil, 
Real graph polynomials, 
in {\sl Progress in Graph Theory}, 
edited by J.~A. Bondy and U.~S.~R. Murty, 
(Academic Press, Toronto) 1984, pp.\ 281--293. 

\ref{cgbk}
C. D. Godsil,
{\sl Algebraic Combinatorics}.
(Chapman and Hall, New York) 1993.

\ref{h-l}
O. J. Heilmann and E. H. Lieb,
Theory of monomer-dimer systems,
{\sl Commun.\ Math.\ Physics, \bf 25} (1972), 190--232.

\ref{lv-pl}
L. Lov\'asz and M. D. Plummer,
{\sl Matching Theory}.
Annals Discrete Math.\ 29, (North-Holland, Amsterdam) 1986.

\ref{neu}
A. Neumaier,
The second largest eigenvalue of a tree,
{\sl Linear Algebra Appl. \bf48} (1982) 9--25.

\bye