Question concerning coclique number bound and Laplacian Matrix

32 Views Asked by At

The question goes as follows:

Let $G$ be a graph on $n$ vertices, $\delta$ its smallest degree, $\alpha$ its coclique number. Let $L$ be its Laplacian matrix, and $\lambda$ it's largest eigenvalue. Prove that:

$$\alpha \leq n \frac{\lambda - \delta}{\lambda}$$