graph with largest eigenvalue at most 2

Question

I encounter this exercise in the chapter of 'Line Graphs and Eigenvalues', GTM207-Algebraic Graph Theory by Godsil & Royle.

I know the answer should be "The only connected graphs having largest eigenvalue 2 are the following graphs (the number of vertices is one more than the index given)."

But I cannot work out the proof of it. Can anyone help me with this? Big thanks!

Answer 1

Here are some hints on how to proceed:

1. If $H$ is a subgraph of $G$, then $\lambda(H) \leq \lambda(G)$. If $G$ is connected and $H$ is a proper subgraph, we have strict inequality.

In particular, any cycle has largest eigenvalue $2$, so if $G$ contains a cycle as a proper subgraph, then $\lambda(G) > 2$.

Which trees have largest eigenvalue $2$?

2. If $\Delta$ is the maximum degree, $\bar{d}$ the average degree, then $\max(\sqrt{\Delta}, \bar{d}) \leq \lambda(G) \leq \Delta$.

This will tell you that $2 \leq \Delta \leq 4$. When $\Delta = 4$, there is only one tree with largest eigenvalue $2$ (I will leave this for you to check).

When $\Delta = 3$, you may verify that the graphs you have shown do have largest eigenvalue $2$. Except for $E_6$, $E_7$, and $E_8$, why does a tree with exactly one vertex of degree $3$ not have largest eigenvalue $2$? What if it has at least $3$ vertices of degree $3$? (these are repeated applications of my first hint)

When $\Delta = 2$, what kind of tree is this?