why there is no graph whose largest eigenvalue, $\lambda_1$, lies in the intervals $(0,1)$ or $(1,\sqrt{2})$?

Question

why there is no graph whose largest eigenvalue, $\lambda_1$, lies in the intervals $(0,1)$ or $(1,\sqrt{2})$? I think it's becaues of if a graph doesn't have any edge then $\lambda_1=0$, if it has one edge, then $\lambda_1=1$ and finally if it has two edges, then $\lambda_1=\sqrt{2}$. For the graphs with more edges, $\lambda_1\geq \sqrt{2}$. Is it correct? Thank you for the help.

Answer 1

You should be more precise: a graph with two edges can still have largest eigenvalue $1$ if those two edges don't share any endpoints. What you mean is: a connected graph with two edges has largest eigenvalue $\sqrt 2$.

Except for that nitpick, you are correct, because the largest eigenvalue of a graph is at least the largest eigenvalue of any subgraph. Any graph either

• is empty, and all its eigenvalues are $0$, or
• has no components with more than one edge, and all its eigenvalues are $1$, $0$, or $-1$, or
• has a component with at least two edges, in which case that component contributes an eigenvalue of at least $\sqrt 2$, by the result above.

We could in theory continue this reasoning if we wanted to. No graph has a largest eigenvalue in the interval $(\sqrt 2, \frac{1+\sqrt5}{2})$, because $\sqrt2$ is the only possible eigenvalue of a connected graph with $2$ edges, and $\frac{1+\sqrt5}{2}$ is the smallest eigenvalue of a connected graph with $3$ edges.