% 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