% \documentstyle{article}
\documentclass[a4paper]{article}
\usepackage{latexsym}
\newtheorem{thm}{Theorem}[section]
\newtheorem{lm}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}

\begin{document}

\title{Eigenvalues and perfect matchings}
\author{Andries E. Brouwer\\
{\small Department of Mathematics,
Technological University Eindhoven,} \\[-3pt]
{\small P.O. Box 513, 5600~MB Eindhoven, The Netherlands}\\[5pt]
Willem H. Haemers\\
{\small Department of Econometrics and Operations Research,
Tilburg University,} \\[-3pt]
{\small P.O.~Box 90153, 5000~LE Tilburg, The Netherlands}
}
\date{}
\maketitle
\begin{abstract}
\noindent
We give sufficient conditions for existence of a perfect matching
in a graph in terms of the eigenvalues of the Laplacian matrix.
We also show that a distance-regular graph of degree $k$ is
$k$-edge-connected.
\end{abstract}

\section{Introduction}

A {\it matching} of a graph $\Gamma$ is a set of mutually disjoint edges.
A matching is {\it perfect} if every vertex of $\Gamma$ is incident with
an edge of the matching.
A perfect matching is also called a {\it 1-factor}.
A set of vertices of $\Gamma$ that is incident with all edges of $\Gamma$
is called a {\it vertex cover} of $\Gamma$.
For perfect matchings in bipartite graphs, Frobenius~\cite{fro}
gave the following characterization.
%
\begin{thm}\label{frob} (Frobenius) A bipartite graph with $v$ vertices
has a perfect matching if and only if each vertex cover has size at
least $v/2$.
\end{thm}
%
Similar results are due to K\"onig~\cite{kon'} and Hall~\cite{hal}.
The characterization of Frobenius implies that the adjacency matrix
of a bipartite graph with no perfect matching must be singular.
So a bipartite graph with only nonzero adjacency eigenvalues has
a perfect matching.
For regular bipartite graphs (of positive degree), Frobenius'
characterization implies that there is always a perfect matching
(K\"onig~\cite{kon}).
Because a graph with adjacency eigenvalues
$\lambda_1\geq\ldots\geq\lambda_v$ is regular if and only if
$v\lambda_1 = \sum_{i=1}^v \lambda_i^2$,
the latter condition can also be interpreted as a sufficient
eigenvalue condition for the presence of a perfect matching in
a bipartite graph.

For perfect matchings in arbitrary graphs we have the following
characterization by Tutte~\cite{tut}.
(An {\it odd component} is a component with an odd number of
vertices.)
%
\begin{thm}
(Tutte)
A graph $\Gamma = (V,E)$ has no perfect matching if and only
if there exists a subset $S\subset V$, such that the subgraph
of $\Gamma$ induced by $V\setminus S$ has more than $|S|$
odd components.
\end{thm}
%
This characterization generalizes Theorem~\ref{frob}
(in a bipartite graph with no perfect matching take $S$
to be a vertex cover of size less than $v/2$),
but by no means it implies that the two mentioned sufficient
conditions for complete matchings in bipartite graphs also
work in general.
Indeed, Figure~1 gives counterexamples for both cases.
The first graph has a nonsingular adjacency matrix and yet no
perfect matching, and the second one is regular with no perfect
matching.
%
\begin{figure}[h]
\begin{center}
\setlength{\unitlength}{3pt}
\begin{picture}(30,14)(0,0)
\put(0,11){\circle*{2}}
\put(6,11){\circle*{2}}
\put(12,11){\circle*{2}}
\put(18,11){\circle*{2}}
\put(24,11){\circle*{2}}
\put(30,11){\circle*{2}}
\put(3,6){\circle*{2}}
\put(15,6){\circle*{2}}
\put(27,6){\circle*{2}}
\put(15,0){\circle*{2}}
\put(0,11){\line(1,0){6}}
\put(12,11){\line(1,0){6}}
\put(24,11){\line(1,0){6}}
\put(0,11){\line(3,-5){3}}
\put(12,11){\line(3,-5){3}}
\put(24,11){\line(3,-5){3}}
\put(3,6){\line(3,5){3}}
\put(15,6){\line(3,5){3}}
\put(27,6){\line(3,5){3}}
\put(15,0){\line(-2,1){12}}
\put(15,0){\line(2,1){12}}
\put(15,0){\line(0,1){6}}
\end{picture}
\hspace{26pt}
\begin{picture}(30,14)(0,0)
\put(-1,11){\circle*{2}}
\put(7,11){\circle*{2}}
\put(11,11){\circle*{2}}
\put(19,11){\circle*{2}}
\put(23,11){\circle*{2}}
\put(31,11){\circle*{2}}
\put(3,6){\circle*{2}}
\put(15,6){\circle*{2}}
\put(27,6){\circle*{2}}
\put(15,0){\circle*{2}}
\put(3,9){\circle*{2}}
\put(3,13){\circle*{2}}
\put(15,9){\circle*{2}}
\put(15,13){\circle*{2}}
\put(27,9){\circle*{2}}
\put(27,13){\circle*{2}}
%
\put(3,9){\line(0,1){4}}
\put(3,9){\line(-2,1){4}}
\put(3,9){\line(2,1){4}}
\put(3,13){\line(2,-1){4}}
\put(3,13){\line(-2,-1){4}}
\put(15,9){\line(0,1){4}}
\put(15,9){\line(-2,1){4}}
\put(15,9){\line(2,1){4}}
\put(15,13){\line(2,-1){4}}
\put(15,13){\line(-2,-1){4}}
\put(27,9){\line(0,1){4}}
\put(27,9){\line(-2,1){4}}
\put(27,9){\line(2,1){4}}
\put(27,13){\line(2,-1){4}}
\put(27,13){\line(-2,-1){4}}
\put(-1,11){\line(4,-5){4}}
\put(11,11){\line(4,-5){4}}
\put(23,11){\line(4,-5){4}}
\put(3,6){\line(4,5){4}}
\put(15,6){\line(4,5){4}}
\put(27,6){\line(4,5){4}}
\put(15,0){\line(-2,1){12}}
\put(15,0){\line(2,1){12}}
\put(15,0){\line(0,1){6}}
\end{picture}
\end{center}
\caption{Graphs without a perfect matching}
\end{figure}
%
In this note we look for sufficient conditions for
perfect matchings in terms of the eigenvalues of the
Laplacian matrix $L$.
We recall that $L$ is related to the adjacency matrix
$A$ by $L=D-A$, where $D$ is the diagonal matrix of
the vertex degrees.
The Laplacian matrix $L$ is positive semi-definite with
row sum 0.
Its eigenvalues will be denoted by $0=\mu_1\leq\mu_2\leq\ldots\leq\mu_v$.
The eigenvalue $\mu_2$ is often called the {\it algebraic connectivity};
$\mu_2=0$ if and only if the graph is disconnected, and $\mu_2\leq\kappa_v$,
where $\kappa_v$ is the vertex connectivity of the graph.
For $k$-regular graphs $D=kI$, and hence the adjacency eigenvalues
$k=\lambda_1\geq\ldots\geq\lambda_v$ are related to the Laplacian
eigenvalues by $\mu_i=k-\lambda_i$ ($i=1,\ldots,v$).
For these and other properties of the Laplacian matrix, see for
example Section~2.5 of \cite{BR}.

We shall show that Tutte's result implies that a graph on
$v$ vertices with $v$ even, whose Laplacian eigenvalues
satisfy $2\mu_2\geq\mu_v$,
has a perfect matching.
For regular graphs with $v$ even, we prove that $\mu_2\geq 1$ is
already sufficient for existence of a perfect matching.

\section{Arbitrary graphs}

In this section we will use an inequality for disconnected
vertex sets in graphs, due to the second author
(see \cite{hae}, Lemma~6.1).
Two disjoint vertex sets $A$ and $B$ in a graph
are called {\it disconnected} if there are no
edges between $A$ and $B$.
%
\begin{lm}\label{ab}
If $A$ and $B$ are disconnected vertex sets of
a graph with $v$ vertices and Laplacian eigenvalues
$0=\mu_1\leq\ldots\leq\mu_v$, then
\[ \frac{|A|\cdot|B|}{(v-|A|)(v-|B|)} \leq
\left( \frac{\mu_v-\mu_2}{\mu_v+\mu_2}\right)^2 . \]
\end{lm}
{~}\\
Another tool is the following elementary lemma.
%
\begin{lm}\label{s}
Let $x_1\ldots x_n$ be $n$ positive integers such that
$\sum_{i=1}^n x_i = k\leq 2n-1$.
Then for every integer $\ell$, satisfying $0 \leq \ell \leq k$,
there exists an $I\subset\{1,\ldots,n\}$ such that
$\sum_{i\in I} x_i = \ell$.
\end{lm}
%
{\bf Proof.}
Induction on $n$. The case $n=1$ is trivial.
If $n\geq 2$, assume $x_1\geq\ldots\geq x_n$.
Then $n-1 \leq k-x_1 \leq 2(n-1)-1$ and we apply the
induction hypothesis to $\sum_{i=2}^n x_i = k-x_1$ with the
same $\ell$ if $\ell\leq n-1$, and $\ell-x_1$ otherwise.
\hfill$\Box$
%
\begin{thm}\label{a}
Let $\Gamma$ be a graph with $v$ vertices, and Laplacian
eigenvalues $0=\mu_1\leq\mu_2\leq\ldots\leq\mu_v$.
If $v$ is even and $\mu_v \leq 2\mu_2$, then $\Gamma$
has a perfect matching.
\end{thm}
%
{\bf Proof.}
Assume $\Gamma=(V,E)$ has no perfect matching.
By Tutte's theorem there exists a set $S\subset V$
of size $s$ (say), such that the subgraph $\Gamma'$ of
$\Gamma$ induced  by $V\setminus S$ has $q > s$ odd
components.
But since $v$ is even, $s+q$ is even, hence $q\geq s+2$.
\\
First assume $v\leq 3s+3$.
Then $\Gamma'$ has at most $2s+3$ vertices and at least $s+2$
components.
By Lemma~\ref{s}, $\Gamma'$ and hence $\Gamma$,
has a pair of disconnected vertex sets $A$ and $B$
with $|A| = \lfloor\frac{1}{2}(v-s)\rfloor$ and
$|B| = \lceil\frac{1}{2}(v-s)\rceil$.
Now Lemma~\ref{ab} implies
\[ \left( \frac{\mu_v-\mu_2}{\mu_v+\mu_2}\right)^2 \geq
\frac{|A|\cdot|B|}{vs+|A|\cdot|B|}
= \frac{(v-s)^2-\epsilon}{(v+s)^2-\epsilon}\ , \]
where $\epsilon=0$ if $v-s$ is even and $\epsilon=1$ if $v-s$
is odd.
Using $v\geq 2s+2$ we obtain
\[ \frac{\mu_v-\mu_2}{\mu_v+\mu_2} > \frac{v-s-1}{v+s} \geq
\frac{s+1}{3s+2} > \frac{1}{3} .\]
Hence $2\mu_2 < \mu_v$.
\\
Next assume $v\geq 3s+4$.
Now $\Gamma'$, and hence $\Gamma$,
has a pair of disconnected vertex sets $A$ and $B$
with $|A|+|B|=v-s$ and $\min\{|A|,|B|\}\geq s+1$,
so $|A|\cdot|B|\geq(s+1)(v-2s-1)>vs-2s^2$.
Now Lemma~\ref{ab} implies
\[ \left( \frac{\mu_v-\mu_2}{\mu_v+\mu_2}\right)^2 \geq
\frac{|A|\cdot|B|}{vs+|A|\cdot|B|} \geq
\frac{vs-2s^2}{2vs-2s^2} =
\frac{1}{2}-\frac{s}{2v-2s}>\frac{1}{4}, \]
by use of $v\geq 3s+4$.
So
\[ \frac{\mu_v-\mu_2}{\mu_v+\mu_2} > \frac{1}{2} > \frac{1}{3}, \]
hence $2\mu_2 < \mu_v$.
\hfill$\Box$\\[6pt]
%
The complete bipartite graphs $K_{m,n}$ with $m\leq n$
have Laplacian eigenvalues $\mu_2=m$ and $\mu_v=v=m+n$.
This shows that $2\mu_2$ can get arbitrarily close
to $\mu_v$ for graphs with $v$ even and no perfect
matching.

\section{Regular graphs}

For regular graphs the condition of the previous section
can be improved.
%
\begin{thm}\label{r}
A connected $k$-regular graph on $v$ vertices with adjacency
eigenvalues $k=\lambda_1\geq\lambda_2\ldots\geq\lambda_v$ and
$v$ even which satisfies
\[ \lambda_3 \leq \left\{\begin{array}{l}
k-1+\frac{3}{k+1} \mbox{ if } k \mbox { is even, }\\[4pt]
k-1+\frac{3}{k+2} \mbox{ if } k \mbox { is odd, }
\end{array}\right. \]
has a perfect matching.
\end{thm}
%
{\bf Proof.}
Let $\Gamma=(V,E)$ be a $k$-regular graph with $v=|V|$ even and
no perfect matching.
By Tutte's theorem there exists a set $S\subset V$ of size $s$
such that $V\setminus S$ induces a subgraph with $q \geq s+2$
odd components $\Gamma_1,~\Gamma_2,\ldots,\Gamma_q$ (say).
Let $t_i$ denote the number of edges in $\Gamma$ between
$S$ and $\Gamma_i$.
Then clearly
$\sum_{i=1}^q t_i \leq ks$, $s\geq 1$, and $t_i\geq 1$
(since $\Gamma$ is connected).
Hence $t_i < k$ and $n_i > 1$ for at least three values of $i$,
say $i=1$, $2$ and $3$.
Let $\ell_i$ denote the largest adjacency eigenvalue of
$\Gamma_i$, and assume $\ell_1 \geq \ell_2 \geq \ell_3$.
Then eigenvalue interlacing (see for example \cite{CDS}, p.19)
applied to the subgraph induced by the union of $\Gamma_1$,
$\Gamma_2$ and $\Gamma_3$ gives $\ell_i\leq\lambda_i$ for
$i=1,~2,~3$.

Consider $\Gamma_3$ with $v_3$ vertices and $e_3$ edges (say).
Then $2e_3 = k n_3 - t_3 \leq n_3(n_3-1)$.
We saw that $t_3 < k$ and $n_3 > 1$, hence $k < n_3$.
Moreover, the average degree $\overline{d}_3$ of $\Gamma_3$ equals
$2e_3/n_3=k-t_3/n_3$.
If $k$ is even, $t_3$ must be even and hence $t_3 \leq k-2$.
If $k$ is odd, $k<n_3$ implies $k\leq n_3-2$ (remember that
$n_3$ is odd).
Hence
\[ \overline{d}_3 \geq \left\{\begin{array}{l}
k-\frac{k-2}{k+1} \mbox{ if } k \mbox { is even, }\\[4pt]
k-\frac{k-1}{k+2} \mbox{ if } k \mbox { is odd. }
\end{array}\right.  \]
Note that $t_3 < n_3$ implies that $\Gamma_3$ cannot be regular.
Next we use the fact (see \cite{CDS}, p.84) that the largest
adjacency eigenvalue of a graph is bounded from below by the
average degree with equality if and only if the graph is regular.
Thus $\overline{d}_3 < \ell_3$.
We saw that $\ell_3\leq\lambda_3$, which finishes the proof.
\hfill$\Box$\\[5pt]
%
The example from the introduction of a $3$-regular connected
graph with an even number of vertices, but no perfect matching
can easily be extended to arbitrary $k\geq 3$
(see \cite{CGS}).
We give the description for $k$ even.
For odd $k$ the construction is similar but slightly more
complicated.
Let $\Gamma'$ be the complete graph $K_{k+1}$ from which a
matching of size $(k-2)/2$ is deleted.
Take $k$ disjoint copies of $\Gamma'$.
Add $k-2$ new vertices and connect each of these vertices to
a vertex of degree $k-1$ in each $\Gamma'$.
This gives a connected $k$-regular graph with $k^2+2k-2$
vertices and no perfect matching.
It is not very difficult to see that both the second and third
largest eigenvalue of this example are equal to the largest
eigenvalue of $\Gamma'$, which equals
$(k-2+\sqrt{k^2+12})/2 = k - 1 + \frac{3}{k+1}+{\cal O}(k^{-2})$.
This shows that for $v$ and $k$ even there exist graphs with no
perfect matching, for which $\lambda_3$ gets arbitrarily close to
the value of Theorem~\ref{r}.

{}From the above it is clear that $v$ even and $\lambda_2 \leq k-1$
implies existence of a perfect matching.
In terms of the Laplacian matrix this translates into:
%
\begin{cor}
A regular graph with an even number of vertices and algebraic
connectivity at least $1$ has a perfect matching.
\end{cor}
%
But we can say more.
The Laplacian matrix of a disjoint union of $v/2$ edges has
eigenvalues $0$ and $2$.
This implies that deletion of the edges of a perfect matching
of a graph $\Gamma$ reduces the eigenvalues of the Laplacian
matrix of $\Gamma$ with at most $2$.
Hence:
%
\begin{cor}
A regular graph with an even number of vertices and algebraic
connectivity $\mu_2$ has at least $\lfloor(\mu_2+1)/2\rfloor$
disjoint perfect matchings.
\end{cor}
%
\begin{cor}\label{diam}
A regular graph with an even number of vertices and
diameter at most $3$ has a perfect matching.
\end{cor}
%
{\bf Proof.} In the proof of Theorem~\ref{r}, we saw that $t_i <
n_i$ for $i=1$, $2$ and $3$. Hence there exist vertices $x$ and $y$
in $\Gamma_1$ and $\Gamma_2$ respectively, that are not ad\-jacent
to a vertex of $S$. Therefore the distance between $x$ and $y$ is at
least~$4.~\hfill\Box$

\section{Distance-regular graphs}

The research for this note was motivated by the question: {\lq}Do
all distance-regular graphs on an even number of vertices have a
perfect matching?{\rq}. (For necessary information on
distance-regular graphs we refer to \cite{BCN}.)

We know of no distance-regular graph that does not satisfy the
condition of Theorem~\ref{r}, but it is not immediately clear
that that condition is fulfilled for all distance-regular graphs.
An example that comes close is the Biggs-Smith graph, where $k=3$ and
$\lambda_2=\lambda_3=(1+\sqrt{17})/2\approx 2.562$.
It may be possible to classify all distance-regular graphs with
second largest eigenvalue larger than $k-1$.

But in the distance-regular case we can prove a stronger result
and have the existence of perfect matchings as an immediate corollary.
%
\begin{thm}\label{ec}
A distance-regular graph of degree $k$ is $k$-edge-connected,
that is, cannot be disconnected by removing fewer than $k$ edges.
Moreover, if $k > 2$ then the only disconnecting sets of $k$ edges
are the sets of $k$ edges on a single vertex.
\end{thm}
%
We conjecture that in fact distance-regular graphs are
$k$-vertex-connected. This is known
for strongly regular graphs (\cite{BM}).
%
\begin{cor}
A distance-regular graph with an even number of vertices
has a perfect matching.
\end{cor}
%
{\bf Proof.}
It is known (see \cite{CGS}), that a $k$-regular graph
with edge connectivity at least $k-1$ on an even number of vertices
has a perfect matching. (The result is also clear from the proof
of Theorem~\ref{r}.)
\hfill$\Box$\\[5pt]
%
Let $\Gamma$ be a distance-regular graph of degree $k > 2$. As
usual, let us write $v$ for the total number of vertices, $d$ for
the diameter and $k_i$ for the number of vertices at distance $i$
from a given vertex. Also, for two vertices $x,y$ at distance $i$,
let $c_i$, $a_i$, $b_i$ be the number of vertices adjacent to $y$,
at distance $i-1$, $i$, $i+1$ (respectively) from $x$. Write
$\lambda := a_1$ and $\mu := c_2$ and $k := k_1$. Finally, let
$\Gamma_i(x)$ be the set of vertices of $\Gamma$ at distance $i$
from the vertex $x$.

First a lemma giving a lower bound for the size of connected
components.

\begin{lm}
(i) Let $S$ be a disconnecting set of vertices of $\Gamma$, and let
$A$ be the vertex set of a component of the complement of $S$ in
$\Gamma$. Fix a vertex $a \in A$ and let $s_i := | S \cap
\Gamma_i(a) |$. Then $|A \cap \Gamma_i(a)| \geq (1 - \sum_{j=1}^i
{s_j \over k_j}) k_i$, so that
$$|A| \geq v - \sum_i {s_i \over k_i} (k_i + ... + k_d).$$
(ii) Let $T$ be a disconnecting set of edges of $\Gamma$, and let
$A$ be the vertex set of a component of $\Gamma$ minus $T$. Fix a
vertex $a \in A$ and let $t_i$ be the number of edges in $T$ that
join $\Gamma_{i-1}(a)$ and $\Gamma_i(a)$. Then $|A \cap \Gamma_i(a)|
\geq (1 - \sum_{j=1}^i {t_j \over c_j k_j}) k_i$, so that
$$|A| \geq v - \sum_i {t_i \over c_i k_i} (k_i + ... + k_d).$$
\end{lm}
%
{\bf Proof}. Because (i) and (ii) are similar, we will only prove
(ii). The case $i=0$ is trivial. Suppose $i\geq 1$, let $e_i$ denote
the number of edges in $\Gamma$ between $A \cap \Gamma_{i-1}(a)$ and
$A \cap \Gamma_i(a)$, and put $m_i := |A \cap \Gamma_i(a)|$. Then
$m_i c_i \geq e_i \geq m_{i-1}b_{i-1}-t_i$. Since
$b_{i-1}/c_{i}=k_{i}/k_{i-1}$, this gives $m_i \geq
m_{i-1}k_i/k_{i-1} - t_i/c_i$, and the inequality follows by
induction.
\hfill$\Box$\\[5pt]
%
For applications of this lemma, it is useful to note that $(k_i +
\ldots + k_d)/k_i \geq (k_{i+1} + \ldots + k_d)/k_{i+1}$ (indeed,
$b_0 \geq \ldots \geq b_{d-1}$ and $c_1 \leq \ldots \leq c_d$
implies $k_i/k_0 \geq \ldots \geq k_d/k_{d-i}$), so that, for
example, part (ii) implies that $$|A| > v(1 - {|T| \over \mu k_2})$$
when $T$ is a disconnecting set of edges none of which is incident
with $a$.
%
\\[5pt]
%
{\bf Proof} of Theorem~\ref{ec}. Suppose we remove (at most) $k$
edges from $\Gamma$, disconnecting this graph, where none of the
components consists of a single vertex. If $B$ is the vertex set of
a component such that each vertex of $B$ is incident with at least
one of the removed edges, then $|B| \leq k$, and each vertex of $B$
is on at least $k - (|B| - 1)$ removed edges with other vertex
outside $B$, so that $|B| (k - |B| + 1) \leq k$. Since by assumption
$|B| > 1$ it follows that $|B| = k$ and the subgraph induced by $B$
is complete. The local graph of $\Gamma$ at a vertex of $B$ is
regular and contains a $(k-1)$-clique, so is a $k$-clique, and also
$\Gamma$ itself is complete, contradiction. This means that every
component has at least $k+1$ vertices, and contains a vertex $b$ not
incident with any of the removed edges.

If $b_1 > 1$, then by the above remark we have for any component
with vertex set $A$ and any vertex $a \in A$ not incident with one
of the removed edges $$|A| > v(1 - {k \over \mu k_2}) = v(1 - {1
\over b_1}) \geq {v \over 2}, $$ so that there is at most one
component, contradiction.

Otherwise $b_1 = 1$, that is, $k = \lambda + 2$. We may assume that
$d \geq 3$, since the case $d = 2$ was treated in \cite{BM}. Then
$c_i \le b_j$ for $i+j \le d$ implies $\mu = 1$. Now the local graph
of $\Gamma$ is a disjoint union of $(\lambda + 1)$-cliques, so
$\lambda = 0$ and $k = 2$, contrary to the assumption. \hfill$\Box$

\begin{thebibliography}{99}
{\footnotesize

\bibitem{BCN}
A.E.~Brouwer, A.M.~Cohen and A.~Neumaier,
{\it Distance-Regular Graphs}, Springer, Heidelberg, 1989.

\bibitem{BM}
A.E.~Brouwer and D.M.~Mesner,
{\it The connectivity of strongly regular graphs},
Eur. J. Combin. {\bf 6} (1985), 215--216.

\bibitem{BR}
R.A.~Brualdi and H.J.~Ryser,
{\it Combinatorial Matrix Theory},
Cambridge Univ. Press, 1991.

\bibitem{CGS}
G.~Chartrand, D.L.~Goldsmith and S.~Schuster,
A sufficient condition for graphs with 1-factors,
{\it Coll. Math.} {\bf 41} (1979), 339--344.

\bibitem{CDS}
D.M.~Cvetkovi\'c, M.~Doob and H.~Sachs,
{\it Spectra of Graphs,}
third edition, Johann Abrosius Barth Verlag, 1995.
(First edition: Deutscher Verlag der Wissenschaften, Berlin 1980;
Academic Press, New York 1980.)

\bibitem{fro}
G.~Frobenius,
\"Uber zerlegbare Determinanten,
{\it Sitzungsberichte der K\"oniglich Preussischen Akademie
der Wissenschaften zu Berlin} (1917), 456--477.

\bibitem{hae}
Willem~H.~Haemers,
Interlacing eigenvalues and graphs,
{\it Linear Alg. Appl.} {\bf 226-228} (1995), 593--616.

\bibitem{hal}
P.~Hall,
On representations of subsets,
{\it J. London Math. Soc.} {\bf 10} (1935), 26--30.

\bibitem{kon}
D.~K\"onig,
\"Uber Graphen und ihre Anwendung auf Determinantentheorie
und Mengenlehre,
{\it Math. Ann.} {\bf 77} (1916) 453--465.

\bibitem{kon'}
D.~K\"onig,
Graphok \'es Matrixok (Graphs and matrices),
{\it Matematikai \'es Fizikai Lapok} {\bf 38} (1931) 116--119.

\bibitem{tut}
W.T.~Tutte,
The factorizations of linear graphs,
{\it J. London Math. Soc.} {\bf 22} (1947), 107--111.

}
\end{thebibliography}

\end{document}
