\documentclass[a4paper]{article}
\usepackage{latexsym}

\newtheorem{Theorem}{Theorem}
\newtheorem{Proposition}[Theorem]{Proposition}
\newtheorem{Lemma}[Theorem]{Lemma}
\newtheorem{Definition}[Theorem]{Definition}
\newtheorem{Corollary}[Theorem]{Corollary}
\newcommand{\qed}{\hfill$\Box$\medskip}
\newcommand{\adj}{\sim}
\newcommand{\tim}{$\times$}

\title{The integral trees with spectral radius 3}
\author{A. E. Brouwer \& W. H. Haemers}
\date{2007-09-11}

\begin{document}
\maketitle

\abstract{There are 11 integral trees with largest eigenvalue 3.}

\section{Integral trees}
A finite graph is called {\em integral} if the spectrum of its
adjacency matrix has only integral eigenvalues.
A {\em tree} is a connected undirected graph without cycles.

In \cite{aeb07} a table is given of the integral trees on at most 48 vertices.
(There are only 25 of these, showing that integral trees are rare objects.)

The nicest result about integral trees is that by Watanabe \cite{Wat79}
that says that an integral tree different from $K_2$ does not have
a complete matching.

All `starlike' integral trees, that is, all integral trees with
at most one vertex of degree larger than 2, were given by
Watanabe and Schwenk \cite{WS79}.

All integral trees of diameter at most 3 were given in \cite{WS79,Gra80}.
See also \cite{Schw80,Cao88}.

Several people have worked on constructing integral trees with
large diameter, and examples with diameters 0--8 and 10 are known,
% diameter 0-4: WS79
% diameter 5: Liu88
% diameter 6: Cao88
% diameter 7: HP07
% diameter 8: HN98
% diameter 10: HP03
see \cite{WS79,Liu88,Cao88,HP07,HN98,HP03}.
% see \cite{Cao88,Cao91,HN98,HP03,HP07,Li98,Liu88,WBHLS07,WL00,WL05,
% WLL99,WLY02,WLZ04}.
It is unknown whether integral trees can have arbitrarily large diameter.
% But see MR1884033 (2002k:05062)

\subsection{Names}
Here we are interested in classification, and in order to indicate
which tree is meant, some notation is needed.
Given a tree, pick some vertex and call it the {\em root}.
Now walk along the tree (depth-first), starting at the root, and when
a vertex is encountered for the first time, write down its distance
to the root.
The sequence of integers obtained is called a {\em level sequence}
for the tree. A tree is uniquely determined by any level sequence.
The parent of a vertex labeled $m$ is the last vertex
encountered earlier that was labeled $m-1$.

For example, the graph $K_{1,4}$ gets level sequence 01111 if the
vertex of degree 4 is chosen as root, and 01222 otherwise.

We use exponents to indicate repetition: 01111 can be written $01^4$
and 0121212 as $0(12)^3$.

\subsection{Classification}
One can try to classify integral trees by their largest eigenvalue
$\lambda_{\rm max}$.

The only example with $\lambda_{\rm max} = 0$ is $K_1$, with spectrum $0$.

The only example with $\lambda_{\rm max} = 1$ is $K_2$,
with spectrum $1$, $-1$.

There are three integral trees with $\lambda_{\rm max} = 2$, namely
01111 (on 5 vertices, with spectrum $2$, $0^3$, $-2$) and
012211 (on 6 vertices, with spectrum $2$, $1$, $0^2$, $-1$, $-2$) and
0121212 (on 7 vertices, with spectrum $2$, $1^2$, $0$, $(-1)^2$, $-2$).
Here exponents denote eigenvalue multiplicities.

(Since all graphs with largest eigenvalue at most 2 are known,
the above follows by simple inspection. See also \S\ref{ev2} below.)

\medskip
In this note we find all integral trees with $\lambda_{\rm max} = 3$.
The table below gives a serial number, the number of vertices $n$,
the diameter $d$, a level sequence and the nonnegative part of the spectrum.
(Note that trees are bipartite, and hence have a spectrum that is symmetric
w.r.t. 0.)

\medskip
\begin{tabular}{lllll}
\# & $n$ & $d$ & graph & spectrum \\
\hline
1 & 10 & 2 & $01^9$ & $3$, $0^8$ \\
2 & 14 & 3 & $012^61^6$ & $3$, $2$, $0^{10}$ \\
3 & 17 & 4 & $0(12)^8$ & $3$, $1^7$, $0$ \\
4 & 17 & 4 & $012^7(12)^4$ & $3$, $2$, $1^3$, $0^7$ \\
5 & 19 & 4 & $012^5(12)^6$ & $3$, $2$, $1^5$, $0^5$ \\
6 & 25 & 5 & $01(23^4)^322(12)^3$ & $3$, $2^3$, $1^3$, $0^{11}$ \\
7 & 26 & 4 & $0(12^4)^5$ & $3$, $2^4$, $0^{16}$ \\
8 & 31 & 6 & $0123^3(1(23)^3)^2(12^4)^21$ & $3$, $2^4$, $1^5$, $0^{11}$ \\
9 & 31 & 6 & $0(123^3)^3(12^4)^3$ & $3$, $2^5$, $1$, $0^{17}$ \\
10 & 37 & 6 & $0(1(23)^3)^51$ & $3$, $2^4$, $1^{11}$, $0^5$ \\
11 & 37 & 6 & $0(123^3)^2(1(23)^3)^312^4$ & $3$, $2^5$, $1^7$, $0^{11}$ \\
\end{tabular}
\medskip

% \begin{Theorem}
\noindent{\bf Theorem}
{\it Let $T$ be a tree with integral eigenvalues and largest eigenvalue 3.
Then $T$ is one of the above 11 graphs.}
\medskip
% \end{Theorem}

\begin{picture}(160,120)(20,30)
\put(100,100){\circle*{4}}
\put(100,124){\circle*{4}}
\put(100,76){\circle*{4}}
\put(100,52){\circle*{4}}
\put(100,28){\circle*{4}}
\put(80,136){\circle*{4}}
\put(80,112){\circle*{4}}
\put(80,88){\circle*{4}}
\put(80,64){\circle*{4}}
\put(80,40){\circle*{4}}
\put(120,136){\circle*{4}}
\put(120,112){\circle*{4}}
\put(120,88){\circle*{4}}
\put(120,64){\circle*{4}}
\put(120,40){\circle*{4}}
\put(60,124){\circle*{4}}
\put(60,100){\circle*{4}}
\put(60,76){\circle*{4}}
\put(60,52){\circle*{4}}
\put(140,124){\circle*{4}}
\put(140,100){\circle*{4}}
\put(140,76){\circle*{4}}
\put(140,52){\circle*{4}}
\put(40,88){\circle*{4}}
\put(40,64){\circle*{4}}
\put(160,88){\circle*{4}}
\put(160,64){\circle*{4}}
\put(144,112){\circle*{4}}
\put(56,112){\circle*{4}}
\put(132,132){\circle*{4}}
\put(68,132){\circle*{4}}
\put(100,124){\line(0,-1){96}}
\put(60,124){\line(5,-3){100}}
\put(140,124){\line(-5,-3){100}}
\put(60,100){\line(5,-3){20}}
\put(60,100){\line(-5,-3){20}}
\put(140,100){\line(5,-3){20}}
\put(140,100){\line(-5,-3){20}}
\put(80,88){\line(0,-1){24}}
\put(120,88){\line(0,-1){24}}
\put(80,64){\line(-5,-3){20}}
\put(120,64){\line(5,-3){20}}
\put(100,52){\line(-5,-3){20}}
\put(100,52){\line(5,-3){20}}
\put(80,136){\line(0,-1){24}}
\put(120,136){\line(0,-1){24}}
\put(80,112){\line(-1,0){24}}
\put(120,112){\line(1,0){24}}
\put(80,112){\line(-3,5){12}}
\put(120,112){\line(3,5){12}}
\end{picture}
\parbox{4cm}{\#8: $0123^3(1(23)^3)^2(12^4)^21$.\\
\vspace{10pt}}

\subsection{A family of examples}
Of the above 11 examples, 8 have a spectral center (cf.~\S\ref{sc} below)
that is a single vertex. Let us give a uniform description of these.

Consider the tree $01^a(12)^b(12222)^c(12333)^d(1232323)^e$.
It has $n = 1+a+2b+5c+5d+7e$ vertices, and spectrum
$0^{a+3c+3d+e-1}$ $(\pm 1)^{b+2e-1}$ $(\pm 2)^{c+d+e-1}$
% (for eigenvalues that vanish at the top)
plus 6 more eigenvalues, roots of
$x^2(x^2-1)(x^2-4) = a(x^2-1)(x^2-4) + bx^2(x^2-4) + cx^2(x^2-1) +
d(x^2-1)(x^2-3) + e(x^2-1)^2$.

(This follows by direct computation of the characteristic polynomial.
These last 6 eigenvalues belong to the eigenvectors that are nonzero
at the top vertex.)

The tree is integral in the cases $01^a$ with $a = t^2$, and $0(12)^b$
with $b = t^2-1$, and $0(12222)^c$ with $c = t^2-4$, and
$b = 0$, $c = 3a+2d-3$, $e = t^2-4a-3d$, where $t$ is the
largest eigenvalue.

For $t = 3$ we find examples \#1, 3, 6--11.
% \#1, \#3, \#7, \#6, \#8, \#9, \#10, \#11.
Many of the integral trees in this family,
and in particular \#8 and \#11, seem to be new.

\section{Generalities}
We start describing some tools we need. Everything is very well known,
except possibly for the concept of `spectral center' of a tree.

\subsection{Perron-Frobenius}
Let $T$ be a connected graph with largest eigenvalue $\lambda$.
Then $\lambda$ has multiplicity 1, and any proper subgraph of $T$
(induced or not) with at least one vertex has largest eigenvalue
strictly less than $\lambda$.
% (See, e.g., \cite{BCN}, Theorem 3.1.1.)

\subsection{Interlacing}
Let $T$ be a graph with eigenvalues
$\theta_1 \ge \theta_2 \ge ... \ge \theta_n$,
and let $x$ be a vertex of $T$.
Let $T \setminus x$ have eigenvalues $\eta_1 \ge ... \ge \eta_{n-1}$.
Then $\theta_1 \ge \eta_1 \ge \theta_2 \ge \eta_2 \ge ... \ge \eta_{n-1}
\ge \theta_n$.
% (See, e.g., \cite{BCN}, Theorem 3.3.1.)

\subsection{Stars}
The star $K_{1,m}$ has spectrum $\sqrt{m}$, $0^{m-1}$, $-\sqrt{m}$.
In particular, if a graph has a vertex of valency $m$, then its
largest eigenvalue is at least $\sqrt{m}$.

\subsection{Godsil's Lemma}
Let $T$ be a tree and $\theta$ an eigenvalue of multiplicity $m > 1$.
Let $P$ be a path in $T$. Then $\theta$ is eigenvalue of $T\setminus P$
with multiplicity at least $m-1$. (\cite{God84})

\subsection{Eigenvalue components}
Given an eigenvalue $\lambda$ of a tree $T$, let $Z = Z(\lambda)$
be the set of vertices where all $\lambda$-eigenvectors vanish.
An {\em eigenvalue component} of $T$ for the eigenvalue $\lambda$
is a connected component of $T \setminus Z$. Each eigenvalue
component has $\lambda$ as an eigenvalue of multiplicity 1.
Let $Z_0 = Z_0(\lambda)$ be the subset of $Z$
consisting of the $z \in Z$ with a neighbour in $T \setminus Z$.
If $T \setminus Z$ has $p$ connected components, and $q = |Z_0|$,
then the eigenvalue $\lambda$ of $T$ has multiplicity $p - q$.
If $\lambda$ is the $j$-th largest eigenvalue of $T$, then
$0 \le |Z_0| \le j-1$.

\subsection{The spectral center of a tree}\label{sc}
There are various combinatorial concepts `center' for trees.
One has the center/bicenter and the centroid/bicentroid.
Here we define a concept of center using spectral methods.

\begin{Proposition}
{\it Let $T$ be a tree (with at least two vertices)
with second largest eigenvalue $\lambda$.
There is a unique minimal subtree $Y$ of $T$ such that
no connected component of $T \setminus Y$ has largest eigenvalue
larger than $\lambda$. We have $1 \le |Y| \le 2$ and
$Z_0(\lambda) \subseteq Y$.}
\end{Proposition}

We call the set $Y$ the {\em spectral center} of $T$.

\medskip\noindent{\bf Proof}\quad
If for some vertex $y$ all connected components of $T \setminus y$
have largest eigenvalue at most $\lambda$, then pick $Y = \{y\}$.
Otherwise, for each vertex $y$ of $T$ there is a unique neighbour
$y'$ in the unique component of $T \setminus y$ that has
largest eigenvalue more than $\lambda$. Since $T$ is finite,
we must have $y'' = y$ for some vertex $y$. Now pick $Y = \{y,y'\}$.
Clearly $Y$ has the stated property and is minimal.
Uniqueness is clear in case $|Y| = 2$.
If no connected component of $T \setminus Y_1$ has largest eigenvalue
larger than $\lambda$, and $Y = \{y\}$, then consider the eigenvalue
components of $\lambda$. If $Z$ is nonempty (in particular, if $\lambda$
has multiplicity more than 1), then necessarily $Z_0 = \{y\}$,
and $Y_1$ must contain $y$, and by minimality $Y_1 = Y$.
If $\lambda$ has multiplicity 1 and $Z$ is empty, then there is
a unique edge $e = pq$ such that the unique $\lambda$-eigenvector
has different signs on $p$ and $q$, and both components of $T \setminus e$
have largest eigenvalue strictly larger than $\lambda$, so that $Y$ must
contain both endpoints of $e$.
\qed

One can be slightly more precise. In fact $Y = Z_0$ when $Z$ is nonempty,
and in this case $|Y|=1$. Otherwise $|Y|=2$ and $Y$ contains the two
endpoints of the edge on which the unique $\lambda$-eigenvector changes sign.

% \medskip
% {\bf Examples} If $T$ is the path $P_n$ with $n$ vertices,
% then $\lambda = 2\cos{\pi/(n+1)}$. If $n$ is odd ...

\subsection{The trees with largest eigenvalue at most 2}\label{ev2}
The trees (integral or not) with largest eigenvalue less than 2
are the Dynkin diagrams $A_n$, $D_n$, $E_6$, $E_7$, $E_8$.
The trees (integral or not) with largest eigenvalue 2 are the
extended Dynkin diagrams $\tilde{D}_m$, $\tilde{E}_6$, $\tilde{E}_7$,
$\tilde{E}_8$.
Every tree with largest eigenvalue larger than 2 contains a
subtree with largest eigenvalue 2.
(This is due to Smith, see, e.g., \cite{BCN}, Theorem 3.2.5.)

\medskip
These traditional Dynkin diagram names mean the following:
$A_n$ is the path with $n$ vertices, that is, has level sequence
$0,1,...,n-1$ ($n \ge 1$).
$D_n$ has level sequence $0,1,1,1,2,...,n-3$ ($n \ge 4$),
so that $D_4$ is 0111 and $D_5$ is 01112.
$E_6$ is 011212, $E_7$ is 0112123, $E_8$ is 01121234.
$\tilde{D}_4$ is $01111$ (that is, is $K_{1,4}$),
$\tilde{D}_m$ has level sequence $0,1,1,1,2,...,n-4,n-3,n-3$ ($n \ge 5$),
so that $\tilde{D}_5$ is $011122$.
$\tilde{E}_6$ is 0121212, $\tilde{E}_7$ is 01123123,
$\tilde{E}_8$ is 011212345.

\medskip
There are 5 integral trees with largest eigenvalue at most 2, namely
$A_1$, $A_2$, $\tilde{D}_4$, $\tilde{D}_5$, $\tilde{E}_6$.
They have 1, 2, 5, 6, 7 vertices, and diameter 0, 1, 2, 3, 4, respectively.

\medskip
Every nonintegral tree with largest eigenvalue at most 2 has a nonintegral
eigenvalue between 1 and 2.
There are 11 trees with largest eigenvalue at most 2 and
a unique nonintegral eigenvalue between 1 and 2, namely
$A_3$, % (eigenvalue $\sqrt{2}$)
$A_4$, % (eigenvalue $(1+\sqrt{5})/2$)
$A_5$, % (eigenvalue $\sqrt{3}$)
$D_4$, % (eigenvalue $\sqrt{3}$)
$D_5$, % (eigenvalue $2 \cos (\pi/8)$)
$E_6$, % (eigenvalue $2 \cos (\pi/12)$)
$\tilde{D}_6$, % (eigenvalue $\sqrt{2}$)
$\tilde{D}_7$, % (eigenvalue $(1+\sqrt{5})/2$)
$\tilde{D}_8$, % (eigenvalue $\sqrt{3}$)
$\tilde{E}_7$, % (eigenvalue $\sqrt{2}$)
$\tilde{E}_8$, % (eigenvalue $(1+\sqrt{5})/2$).
They have 3, 4, 5, 4, 5, 6, 7, 8, 9, 8, 9 vertices,
and diameter 2, 3, 4, 2, 3, 4, 4, 5, 6, 6, 7, respectively.


\section{Proof of the theorem}

It is straightforward to check that the 11 graphs have the spectrum
given in the table. Conversely, a computer search shows that there
are no other examples. Below we show how to reduce the search space
so that the computer search becomes feasible.

\subsection{Finitely many examples}
Consider a tree $T$ with no other eigenvalues than
$\pm 3$, $\pm 2$, $\pm 1$, $0$.

The diameter of a connected graph is smaller than the number of
distinct eigenvalues. It follows that $T$ has diameter at most 6.

The 9-star $K_{1,9}$ has largest eigenvalue 3 (it is \#1 on the list),
and a graph that strictly contains it has larger eigenvalue.
Thus, if $T$ is not $K_{1,9}$ then its maximum valency is at most 8.

Now that both diameter and valency have been bounded, there are
only finitely many possibilities.

\subsection{Vertices of high degree}
By interlacing, if $x$ is any vertex of $T$, then at most one
component of $T \setminus x$ has largest eigenvalue larger than 2.
In particular, at most one component of $T \setminus x$ has
largest degree more than 4.
It follows that two vertices of degree more than 5 must be adjacent,
and there can be at most two such vertices. The largest eigenvalue
of the bi-star $012^r1^m$ obtained by adding an edge joining the
central vertices of $K_{1,m}$ and $K_{1,r}$ is the largest root
of the polynomial $(X^2-m)(X^2-r) - X^2$. It follows that if this
bi-star is an induced subgraph (i.e., if there are two adjacent vertices
of degrees $m+1$ and $r+1$) then $(9-m)(9-r)-9 \ge 0$ with equality only
when this bi-star is all of $T$.
Consequently, a neighbour of a vertex of degree 8 has degree at most 5,
and a neighbour of a vertex of degree 7 has degree at most 7, and two
adjacent vertices of degree 7 occur only in $012^61^6$, graph \#2 on the list.

\subsection{Components of a tree minus a point}

Let $T$ be an integral tree with largest eigenvalue 3, and $x$ a vertex of $T$.
Since the spectrum of $T \setminus x$ is the union of the spectra
of its connected components, it follows by interlacing that among
the components of $T \setminus x$ there is at most one that has a
(unique) nonintegral eigenvalue between 1 and 2,
and at most one that has an eigenvalue larger than 2.

In particular, all components of $T \setminus x$ are one of
$A_1$, $A_2$, $\tilde{D}_4$, $\tilde{D}_5$, $\tilde{E}_6$,
except for at most one with largest eigenvalue larger than 2,
and at most one that is nonintegral but has largest eigenvalue
at most 2 and a unique nonintegral eigenvalue between 1 and 2.

\medskip
None of $\tilde{D}_7$, $\tilde{D}_8$, $\tilde{E}_7$ can occur
as component of $T \setminus x$ when there are other components
not reduced to a single point.
Indeed, the point of attachment $w$ in such a component must be
the middle vertex (or one of the two middle vertices), otherwise
$T$ gets diameter larger than 6. But then $T\setminus w$ has two
nonintegral eigenvalues between 1 and 2,
% (namely $\sqrt{2},\sqrt{3}$ or twice $\sqrt{3}$ or twice $\sqrt{2}$),
impossible.
This argument applied to $\tilde{D}_6$ shows that it cannot be
attached at the middle node, otherwise $T$ gets eigenvalue $\sqrt{2}$.

\medskip
Let $Y$ be the spectral center of $T$. If $Y = \{y\}$,
then $n \le 1 + 56 = 57$ since $y$ has valency at most 8
and all components of $T \setminus y$ have at most 7 vertices.
Otherwise $Y = \{y,y'\}$, and $n \le 2 + 77 = 79$ since we saw
that the sum of the valencies of two neighbours is at most 13.

\subsection{Diameter}
Let $S_1$, $S_2$ be disjoint subtrees of $T$ at mutual distance $e$
and with respective diameters $d_1$, $d_2$. Then $T$ has diameter
at least $\lceil d_1/2 \rceil + e + \lceil d_2/2 \rceil$, so this
expression is at most 6.
That means that the last estimate can be improved:
if all components of $T \setminus \{y,y'\}$ have largest eigenvalue
at most 2, then $n \le 2+49+20 = 71$.

\subsection{All possible spectra}
Consider a tree $T$ on $n$ points, with adjacency matrix $A$ with
spectrum $\pm 3$, $(\pm 2)^a$, $(\pm 1)^b$, $0^c$, where
exponents denote multiplicities.
Since the number of eigenvalues equals $n$, we have $n = 2a+2b+c+2$.

The number of closed walks of length $s$ in $T$ equals ${\rm tr\,} A^s$.
In particular we find ${\rm tr\,} A^2 = 2(n-1)$ (twice the number of edges),
and it follows that $9+4a+b = n-1$, that is, $8+2a = b+c$.

Thus, the spectrum is given by the pair $(n,a)$.
% b+c=2a+8, 2b+c=n-2a-2,
% b=n-4a-10, c=6a+18-n
Now that $n$ is bounded, we can enumerate all pairs $(n,a)$ with
$n \le 71$ and $b = n-4a-10 \ge 0$ and $c = 6a+18-n \ge 0$.
% $n = 2a+2b+c+2 \le 71$ and $8+2a = b+c$.
There are 251 of those.

% Willem merkt op dat in T\{x,x'} er hooguit a+1 componenten zijn
% met eigenwaarde groter dan 1, zodat n <= 2 + 7(a+1) + 2(10-a) = 29+5a.
% Voorts, dat als er precies a+1 zulke componenten zijn, dan moet er
% minstens een aan x' hangen, en n <= 2 + 7a + 5 + 2(10-a) = 27+5a.
% Kortom, er geldt n <= 27+5a. Maar dat helpt niet. % cond#6

\subsection{Eigenvalue components}
Let 2 be an eigenvalue of the tree $T$ with multiplicity $a$.
Let $Z$ be the set of vertices where all 2-eigenvectors vanish,
and let $Z_0$ be the subset of the $z \in Z$ with a neighbour
in $T \setminus Z$. Then $T \setminus Z$ has $p = a+q$ connected
components, where $q = |Z_0|$. Each connected component has size
at least 5, so $n-q \ge n-|Z| \ge 5p$. It follows that if $a > 1$,
then $q \ge 1$ and $n-1 \ge 5(a+1)$.
Now 198 spectra are left. % cond#1

\medskip
If $C,D$ are two components of $T \setminus Z$ and $x$ a vertex
nonadjacent to both, then $x$ cannot separate $C$ and $D$,
since that would give two components of $T \setminus x$
both with largest eigenvalue larger than 2.
It follows that $q \le 2$, and if $q = 2$ then the two vertices
in $Z_0$ are neighbours.

\medskip
If there is one component of $T \setminus Z$ with largest eigenvalue
greater than 2 then $q = 1$. % otherwise T has 2 evs larger than 2
Every other component is one of $\tilde{D}_m$ $(4 \le m \le 6)$,
$\tilde{E}_6$.

\medskip\noindent\begin{center}\begin{tabular}{@{}llllllll@{}}
comp & diam & size & ev in (2,3) & ev in (1,2) & val 4 & val 3 & val 2 \\
\hline
$\tilde{D}_4$ & 2 & 5 & 0 & 0 & 1 & 0 & 0 \\
$\tilde{D}_5$ & 3 & 6 & 0 & 0 & 0 & 2 & 0 \\
$\tilde{D}_6$ & 4+ & 7 & 0 & 1 & 0 & 2 & 1 \\
$\tilde{E}_6$ & 4 & 7 & 0 & 0 & 0 & 1 & 3 \\
? & ? & $\ge 11$ & 1 & ? & ? & ? & ? \\
\end{tabular}\end{center}


\subsection{Matchings}
By Watanabe \cite{Wat79}, the tree $T$ does not have a complete matching.
But the characteristic polynomial of $T$ equals
$\phi_T(X) = \sum_k (-1)^k a_{2k} X^{n-2k}$, where $a_{2k}$ is the
number of ways one can choose $k$ pairwise disjoint edges in $T$.
That means that $\phi_T(X)$ has zero constant term, so that there
is an eigenvalue 0, and $c \ne 0$. Now 189 spectra are left. % cond#5

\subsection{Degree sequences}
Let $d_x$ denote the degree of the vertex $x$.
Then $\sum d_x = 2(n-1)$, twice the number of edges.
And ${\rm tr} A^4 = 2\sum d_x^2 - 2(n-1)$ so that
$\sum d_x^2 = 81+16a+b+n-1 = 90+20a+2b = 70+12a+2n$. % = 40+5n-3b$.
We can solve this for all possible degree sequences $(d_x)$,
recalling that there are at most two vertices of degree more than 5.
If there is no possible sequence, the triple can be dropped.
Now 185 spectra are left. % cond#3
% (That is, in 4 cases there is no possible degree sequence at all.
% By adding further conditions on degree sequences we get stronger results.)

\medskip
If the largest degree is smaller than $a+1$ then $q=2$ and
$n-2 \ge 5(a+2)$. In this case the sum of the two largest degrees
must be at least $a+4$. Now 141 spectra are left. % cond#7

\subsection{Eigenvalue components (2)}
Each component of size 5 of $T \setminus Z$ contains a point
of degree 4 or 5. Components for which no such point is
available have size at least 6.
% really 5, otherwise diameter larger
Now 109 spectra are left. % cond#9

The number of components is $p = a+q$, and all these components
contain a point of valency 3 or 4, after attachment 3 or 4 or 5.
So, there must at least be $p$ points of valency 3, 4, or 5,
and at least $p+q$ points of valency at least 3.
Now 92 spectra are left. % cond#10

% Hmm, except that there might be a component with larger ev.
% If only 1,2,5+ and topologically a star, then no ev 2.
% If only 1,2,5+ and at least two 5+, then one differs from
% the point of attachment and we get two ev larger than 2
% unless the lower was precisely 5 and the upper has a K_{1,4}
% component. But then it belongs to Z. Contradiction.
% So, still OK.

The point of attachment of a component $\tilde{E}_6$ cannot be
one of its leaves, since that would give $T$ too large a diameter.
It follows that if a component does not contain points of valency 4 or 5,
then it contains at least two points of valency 3.
Now 76 spectra are left. % cond#11

(Note that here an unknown component of largest eigenvalue larger
than 2 does not harm: if it has no vertices of valency 4 or more,
and at most a single vertex of valency 3, then the component is
topologically a star, and if it has eigenvalue 2 that must be
the largest eigenvalue because the eigenvector has constant sign.
And if there is a vertex of valency 6 or more, then it must be
the point of attachment (otherwise $T$ gets two eigenvalues larger
than 2), and therefore unique, and now again the 2-eigenvector
has constant sign, contradiction.)

If a component does not contain points of valency 3 or at least 5,
then it must also contain a point of valency 2. (A $\tilde{D}_4$
component has a point of attachment: either its center, which then
gets valency 5, or a leaf, which then gets valency 2.)
Now 73 spectra are left. % cond#12

% A component with eigenvalue 2 and largest eigenvalue more than 2
% must have at least 11 vertices. % e.g. K_{1,4}~*~K_{1,4}

% If some component has diameter 5 or 6, or is $\tilde{D}_6$,
% then $q = 1$ and all other components have diameter 2.
% But the only trees of diameter 2 are the stars, and $K_{1,m}$
% has eigenvalue 2 only for $m = 4$. In particular, if some component is
% $\tilde{D}_6$ or $\tilde{D}_7$ then all other components are $\tilde{D}_4$.
% Moreover, the points of attachment are determined, so that the tree
% $T \setminus Z \cup \{z\}$ (where $z$ is the unique point of $Z$
% adjacent to $T \setminus Z$) is uniquely determined by
% the number of components $\tilde{D}_4$.
% The remaining components of $T\setminus z$ cannot have nonintegral
% eigenvalues between 1 and 2, so are $K_1$ or $K_2$ or
% $K_{1,m}$ with $m > 4$.

\subsection{Walks of length 6}
${\rm tr} A^6$ counts the number of closed walks of length 6.
We find
$$3^6 + 2^6a + b = \sum d_x^3 - 3 \sum d_x^2 + 2(n-1) + 3 \sum_e d_xd_y$$
where the last sum is over all unordered edges $e = xy$.
Given the degree sequence, this allows us to compute $\sum_e d_xd_y$.
The maximal possible value of $\sum_e d_xd_y$ is obtained by ordering
the vertices by decreasing degree, and building the tree by
starting with the vertex of highest degree, and each step attaching
a new vertex of highest possible degree to the vertex of highest degree
in the tree that still has room left.
If this maximum is smaller than the computed $\sum_e d_xd_y$,
we can discard the degree sequence. Now 59 spectra are left. % cond#8

% \medskip
% We saw that the maximal number of pairwise disjoint edges equals
% the number of positive eigenvalues.
% If $T$ has only one positive eigenvalue, then it must be a star $01^m$.
% But that has largest eigenvalue $\sqrt{m}$, so $m = 9$ and we have \#1.
% If $T$ has only two positive eigenvalues, then there cannot be three
% vertices of degree 3 or more. Watanabe and Schwenk \cite{WS79} settled
% the case with 0, or 1, or 2 adjacent such vertices, and found the stars
% $01^m$ where $m$ is a square, and the bi-star $012^r1^m$ where
% $X^4-(m+r+1)X^2+mr$ has 4 integral roots. If 3 is an eigenvalue
% we must have $m = r = 6$, that is, case \#2.
% Remains the case with 2 nonadjacent vertices of degree 3 or more,
% separated by a single vertex of degree 2, say $012^m12^r$.
% Now $n=m+r+3$ and 0 has multiplicity $m+r-1 = n-4$.
% The equation for the remaining eigenvalues becomes $(X^2-m-1)(X^2-r-1) = 1$,
% so both factors must be equal, and $m=r$, and $X^2 = m$ or $X^2 = m+2$,
% and the largest eigenvalue has multiplicity 2, impossible.
% Therefore $T$ has more than two positive eigenvalues, i.e. $a+b+1 \ge 3$.
% Now 222 spectra are left.
% [after the #leaves <= 9+3a this argument here is good for a single triple,
% namely n=14  0^10, 2^1, 3, #2]

\subsection{Matchings (2)}
As already remarked, the characteristic polynomial of $T$ equals
$\phi_T(X) = \sum_k (-1)^k a_{2k} X^{n-2k}$, where $a_{2k}$ is the
number of ways one can choose $k$ pairwise disjoint edges in $T$.
That means that the product of the nonzero eigenvalues is the
number of ways of chosing $m$ disjoint edges, where $n-2m = c$
is the multiplicity of the eigenvalue 0.

Thus, the maximum number of pairwise disjoint edges equals $m = a+b+1$.
The number of non-leaves must be at least this much since no edge
contains two leaves. This provides an upper bound $9+3a$ for the number
of vertices of degree 1. % cond#4 - does not really help
In case of equality, the number of ways to choose $m$ disjoint edges
is the product of the number of leaves attached to the non-leaf vertices.

For example, if $n = 16$ and the positive spectrum is 3, 2, $1^2$, $0^8$,
and the degree sequence is 12\tim 1 1\tim 2 1\tim 3 1\tim 5 1\tim 8,
then the product of the nonzero eigenvalues is 36,
and this is the product of 4 factors,
namely 1, 1..2, 1..4, 1..7. The only possibility is 1*2*3*6, so that
the `internal graph', after removal of the 12 leaves, is a path.
But if the internal graph is a path, no nonzero eigenvalue can have
multiplicity larger than 1, since the eigenvector is uniquely determined.
So, no such graph exists.

\subsection{Finish}
At this point 58 spectra are left, all with $n \le 45$.
A computer search for all trees on at most 45 vertices,
with diameter at most 6, maximum valency at most 8,
and integral spectrum now finishes the job.
%
% treepol -u6 -d8 -n1..45 takes precisely 100 min.

\section{Application of Godsil's Lemma}
It is possible to do everything by hand, avoiding the use
of a computer. (But the proof becomes long and tedious.)

The first tool to use in such a hand proof is Godsil's Lemma.
It allows one to dispose of the cases of diameter 5 and 6.
Let us show here a small fragment.

\medskip
Suppose $T$ has diameter 6, the maximum possible value.
Then $a,b,c$ are nonzero.
Let $P$ be a path of length 6, that is, with 7 vertices.
By Godsil's Lemma, the forest $T \setminus P$ has spectrum
$(\pm 2)^{a-1}$, $(\pm 1)^{b-1}$, $0^{c-1}$, and hence is integral,
and each tree in that forest is one of $A_1$, $A_2$, $\tilde{D}_4$,
$\tilde{D}_5$, $\tilde{E}_6$. The number of trees in that forest
is the number of vertices minus the number of edges, that is, is
$(n-7) - (4a-4+b-1) = 8$.

Suppose that at least one of the components of $T \setminus P$
is $\tilde{D}_5$, or $\tilde{E}_6$, or $\tilde{D}_4$ (attached at a leaf).
Then such a component must be joined to the middle vertex $p$ of $P$,
otherwise the diameter would become larger than 6.
Now there are three paths $P_i$ $(i=1,2,3)$ of length 3 starting at $p$
such that for $i \ne j$ the union $P_i \cup P_j$ is a path of length 6.

Let $\phi(T)$ denote the characteristic polynomial of a tree $T$.
Let $Q_i$ be the connected component of $T\setminus p$ containing
$P_i \setminus p$. Since the spectrum of $T \setminus (P_i \cup P_j)$
is the same for all choices of $i \ne j$,
% that is Q_i+(Q_j\P_j)+(Q_k\P_k) has same spectrum
it follows that $\phi(Q_i)/\phi(Q_i \setminus P_i)$ is the same
for all $i$.

Now $\phi(Q_i) / \phi(Q_i \setminus P_i)$ in the three cases
$\tilde{D}_5$, $\tilde{E}_6$, $\tilde{D}_4$ (attached at a leaf)
equals $(X^2-4)(X^2-1)/X$, $(X^2-4)X$, $(X^2-4)X$.

If one of the $Q_i$ is of shape $\tilde{D}_5$, then all are,
and $T\setminus p$ has spectrum $(\pm 2)^{a+1}$, $(\pm 1)^{b+1}$, $0^{c-3}$,
impossible, since the multiplicity of $0$ cannot decrease by 3
when a single point is removed.

So, only the shapes $\tilde{D}_4$ and $\tilde{E}_6$ occur,
and $T\setminus p$ has spectrum $(\pm 2)^{a+1}$, $(\pm 1)^{b-1}$, $0^{c+1}$,
and has $(n-1)-(4a+4+b-1) = 6$ components.

Let $T\setminus p$ have $n_1$, $n_2$, $n_{5a}$, $n_{5b}$, $n_7$
components of shape $A_1$, $A_2$, $\tilde{D}_4$ (attached at the center),
$\tilde{D}_4$ (attached at a leaf), $\tilde{E}_6$, respectively.
Then $n_1 + n_2 + n_{5a} + n_{5b} + n_7 = 6$.
The condition for $T$ to have eigenvalue 3 is
$5n_1 + \frac{45}{8}n_2 + 9n_{5a} + 6n_{5b} + 8n_7 = 45$.
It follows that $n_2 = 0$, and we have one of
$(n_1,n_{5a},n_{5b},n_7) = (1,0,0,5)$, $(0,1,2,3)$, $(1,2,1,2)$,
$(2,3,0,1)$, $(0,3,3,0)$. These correspond to the graphs
\#10, \#11, \#8, \#6 and \#9, respectively.

\medskip
This settles the case of a path $P$ of length 6 where one of
the components of $T \setminus P$ is of shape
$\tilde{D}_5$, or $\tilde{E}_6$, or $\tilde{D}_4$ (attached at a leaf).
Remain the cases where all components of $T \setminus P$ are of shape
$A_1$, $A_2$, or $\tilde{D}_4$ (attached at the center),
and that where $T$ has diameter smaller than 6.

The case of diameter 5 is handled like that of diameter 6:
if $P$ has length 5, then by Godsil's Lemma $T \setminus P$
has eigenvalues $\theta$, $(\pm 2)^{a-1}$, $(\pm 1)^{b-1}$, $0^{c-1}$
for a single eigenvalue $\theta$. But then $\theta = 0$ and the
spectrum is $(\pm 2)^{a-1}$, $(\pm 1)^{b-1}$, $0^c$, so is
known and integral again.

\begin{thebibliography}{999}

\bibitem{aeb07} A. E. Brouwer,\\
{\tt \verb#http://www.win.tue.nl/~aeb/graphs/integral_trees.html#}

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

\bibitem{Cao88} Z. F. Cao,
{\it Integral trees of diameter R $(3 \le R \le 6)$} (in Chinese),
Heilongjiang Daxue Ziran Kexue Xuebao {\bf 2} (1988) 1--3, 95.
% elsewhere: J. Heilongjiang University
% classifies the case of diameter 3

% Zhen Fu Cao
% \bibitem{Cao91} Z. F. Cao,
% {\it Some new classes of integral trees with diameter 5 or 6} (in Chinese),
% J. Systems Sci. Math. Sci. {\bf 11} (1991), no.1, 20--26.

\bibitem{God84} C.D. Godsil,
{\it Spectra of trees},
Annals of Discrete Mathematics {\bf 20} (1984) 151-–159.

\bibitem{Gra80} R. L. Graham,
{\it On a Diophantine Equation Arising in Graph Theory},
Europ. J. Comb. {\bf 1} (1980) 107–112.

\bibitem{HS74} F. Harary and A. J. Schwenk,
{\it Which graphs have integral spectra?},
In: Graphs and Combinatorics,
% (eds. R. Bari and F. Harary),
% (Proc. Capital Conf., George Washington Univ., Washington, D.C., 1973),
Lecture Notes in Mathematics 406, Springer-Verlag, Berlin (1974), 45--51.

% \bibitem{Hic97} P. H\'{\i}c,
% {\it On balanced integral trees of diameter 6}, CO-MAT-TECH ù97, 5.
% vedeck´a konferencia s medzin´arodnou ´u´cas´tou,
% Trnava 14--15 (1997), 125--129.

\bibitem{HN98} P. H\'{\i}c and R. Nedela,
{\it Balanced integral trees}, Math. Slovaca {\bf 48} (1998) 429--445.
% It is shown that there are infinitely many balanced integral trees
% of diameter 8, but there are none of diameter $4k+1$ for $k \ge 1$.

% Pavel H\'{\i}c and Milan Pokorn\'{y}
\bibitem{HP03} P. H\'{\i}c and M. Pokorn\'{y},
{\it On integral balanced rooted trees of diameter 10},
Acta Univ. M. Belii Math {\bf 10} (2003) 9--15.

\bibitem{HP07} P. H\'{\i}c and M. Pokorn\'{y},
{\it There are integral trees of diameter 7},
Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. {\bf 18} (2007) 59--63.

% Maosheng Li, Wensheng Yang, Jiabao Wang
% \bibitem{LYW00} M. S. Li, W. S. Yang and J. B. Wang,
% {\it Notes on the spectra of trees with small diameters} (in Chinese),
% J. Changsha Railway University 18 (2000) 84--87.

% \bibitem{LL87} X. L. Li and G. N. Lin,
% {\it On trees with integer eigenvalues},
% % or: On the problem of integral trees
% Kexue Tongbao (Chinese Ed.) {\bf 32} (1987), no.11, 813--816 (in Chinese),
% or {\it On integral trees problems},
% Kexue Tongbao (English Ed.) {\bf 33} (1988), no.10, 802--806 (in English).

% \bibitem{LW00} X. L. Li and L. G. Wang,
% {\it Integral trees---a survey} (in Chinese),
% Chinese Journal of Engineering Math. (or Gongcheng Shuxue Xuebao)
% {\bf 17} (2000), no.suppl., 91--93, 96.

% \bibitem{Li98} Y. Li,
% {\it A new class of integral trees with diameter 5} (in Chinese),
% J. Math. Res. Exposition {\bf 18} (1998), no.3, 435--438.

% Ru Ying Liu
\bibitem{Liu88} R. Y. Liu,
{\it Integral trees of diameter 5} (in Chinese),
J. Systems Sci. Math. Sci. {\bf 8} (1988), no.4, 357--360.
%  Let $T(m,r)$ be the graph obtained by connecting the centers
%  of the two star graphs $K_{1,m}$ and $K_{1,r}$,
%  and let $T^* (m,r,t)$ be the graph obtained by connecting
%  each vertex of $T(m,r)$ to $t$ new vertices.
%  The following theorems are proved: For each integral solution
%  $(b,s)\not=(1,1)$ of the Pell equation $x^2-2y^2=-1$,
%  and defining $m=2s^2$, $r=2b^2$, and $t =((b^2-1)/4)^2$,
%  $T^*(m,r,t)$ is an integral tree of diameter 5.
%  As a corollary there exist infinitely many integral trees of diameter 5.

% \bibitem{Liu88a} R. Y. Liu,
% {\it Some new families of trees with integral eigenvalues} (in Chinese),
% J. Qinghai Normal University {\bf 3} (1988) 1--5.

% \bibitem{R06} I. K. Redchuk,
% {\it Separating functions and spectra of starlike graphs},
% preprint, 2006.

% \bibitem{Ren00} Haizhen Ren,
% {\it On integral trees with diameter four},
% J. Qinghai Normal Univ. {\bf 1} (2000) 8--11.

\bibitem{Schw80} A. J. Schwenk,
{\it Trees with integral eigenvalues},
Problem 23 in: {\it A collection of open problems},
M.~Capobianco, S.~Maurer, D.~McCarthy and J.~Molluzzo (eds.),
pp. 565--590 in: Proc. Second International Conference on
Combinatorial Mathematics (A.~Gewirtz and L.~V.~Quintas, Eds.),
Ann. New York Acad. Sci. {\bf 319} (1980) 582--583.

\bibitem{Wthesis} Ligong Wang,
{\it Integral trees and integral graphs},
Ph. D. thesis, Univ. Twente, 2005.

% Ligong Wang, Hajo Broersma, Cornelis Hoede, Xueliang Li, Georg Still
% \bibitem{WBHLS07} L. G. Wang, H. J. Broersma, C. Hoede, X. L. Li
% and G. Still,
% {\it Integral trees of diameter 6},
% Discrete Applied Mathematics 155 (2007) 1254--1266.
% In this paper, the trees T(p,q)*T(r,m,t) and K''1'',''s*T(p,q)*T(r,m,t)
% of diameter 6 are defined.

% \bibitem{WL00} L. G. Wang and X. L. Li,
% {\it Some new classes of integral trees with diameters 4 and 6},
% Australas. J. Combin. 21 (2000), 237--243.

% Ligong Wang, Xueliang Li
% \bibitem{WL05} L. G. Wang and X. L. Li,
% {\it Integral trees with diameters 5 and 6},
% Discrete Math. {\bf 297} (2005) 128--143.

% \bibitem{WLL99} L. G. Wang, X. L. Li and R. Y. Liu,
% {\it Integral trees with diameter 6 or 8},
% 6th Twente Workshop on Graphs and Combinatorial Optimization
% (Enschede, 1999), 6 pp. (electronic),
% Electron. Notes Discrete Math. 3, Elsevier, Amsterdam (1999).

% \bibitem{WLY02} L. G. Wang, X. L. Li and X. J. Yao,
% {\it Integral trees with diameters 4, 6 and 8},
% Australas. J. Combin. {\bf 25} (2002), 29--44.

% Ligong Wang, Xueliang Li, Shenggui Zhang
% \bibitem{WLZ04} L. G. Wang, X. L. Li and S. G. Zhang,
% {\it Families of integral trees with diameters 4, 6 and 8},
% Discrete Appl. Math. {\bf 136} (2004) 349--362.
% (or L.G. Wang, X.L. Li and S.G. Zhang,
% Some new families of integral trees with diameters 4 and 6,
% Electronic Notes in Discrete Math. vol. 8 (2001)).

\bibitem{Wat79} M. Watanabe,
{\it Note on integral trees},
Math. Rep. Toyama Univ. {\bf 2} (1979) 95--100.

\bibitem{WS79} M. Watanabe and A. J. Schwenk,
{\it Integral starlike trees},
J. Austral. Math. Soc. (A) {\bf 28} (1979) 120--128.

% Dashen Xu
% \bibitem{Xu96} D. S. Xu,
% {\it A note on the integral trees with diameter 4} (in Chinese),
% J. Qinghai University 14 (1996) 16--18.

% \bibitem{Xu97} D. S. Xu,
% {\it Some new classes of the integral trees with diameter 4} (in Chinese),
% J. Hebei University 17 (1997) 12--16.

% Xiangyuan Yao,
% Integral trees and integral digraphs (Chinese),
% MSc. Thesis, Northwestern Polytechnical University, China, 2001.

% Pingzhi Yuan
% \bibitem{Yuan98} P. Z. Yuan,
% {\it Integral trees of diameter 4} (in Chinese),
% J. Systems Sci. Math. Sci. 18 (1998), no.2, 177--181.

% \bibitem{ZT00} D. L. Zhang and S. W. Tan,
% {\it Integral trees of diameter 4} (in Chinese),
% J. Systems Sci. Math. Sci. 20 (2000) 330--337.

% De-long Zhang and Lan-yong Wei
% \bibitem{ZW98} D. L. Zhang and L. Y. Wei,
% {\it On the existence of integral trees of diameter 4} (in Chinese),
% J. Guangxi Institute of Technology 9 (1998) 1--5.

\end{thebibliography}

\end{document}
