Spectral analysis

57 Views Asked by At

Prove that graph with the largest eigenvalue less than $2$ is acyclic.

I tried to prove the above statement by taking into consideration the maximum degree. Maximum degree is greater than equal to the largest eigenvalue. So the maximum degree is going to be less than $2$. I don't know what to do further.

Thank you

1

There are 1 best solutions below

0
On BEST ANSWER

Your assumptions that "the maximum degree is going to be less than 2" is false. Let $\lambda_1$ be the largest (adjacency I suppose?) eigenvalue of your graph, you have $$ \left\{ \begin{array}{l} \frac{2m}{n}=AvgDeg_G \leq \lambda_1 \leq \Delta_G\\ \lambda_1 < 2 \end{array} \right.$$

This does not give you $\Delta_G < 2$. This would be much stronger than acyclic. You could have an acyclic graph with vertices of degree 2.

In order to solve your problem : suppose that your graph include a cycle. Using repeating interlacing, show that the largest eigenvalue of your graph must be larger then the largest eigenvalue of the cycle.

But note that the sprectrum of a cycle is known : $$\{ 2-2\cos\frac{2k\pi}{n}, k=0,\ldots,n-1\}$$ In particular 2 is the largest eigenvalue of this cycle (this could also be seen as a cycle is 2-regular).

Then the largest eigenvalue of your graph must be greater or equal to 2: $$G \text{ contains a cycle }\Rightarrow \lambda_1 \geq 2$$ Hence $$\lambda_1 < 2\Rightarrow G \text{ cis acyclic}$$