# Let G be a graph with largest eigenvalue λ and largest degree ∆. Prove that λ ≥ √ ∆.

The eigenvalue is for the adjacency matrix. I think there must be some clever inequality chain using the product of the matrix $$A^2$$ by an eigenvector, but i couldn't get it to work.

Hint: Let $$v$$ be a vertex of degree $$\Delta$$, and $$\chi$$ be the vector in $$\mathbb{R}^{V(G)}$$ such that $$\chi(v) = \sqrt{\Delta}$$; $$\chi(u) = 1$$ for all $$u \in N_G(v)$$; and $$\chi(w) = 0$$ for every other vertex $$w$$. Then from a fact in linear algebra, the largest eigenvalue $$\lambda$$ satisfies the following:
$$\lambda \ge \frac{\chi^{T}{\bf{A}}\chi}{\chi^T\chi}.$$
So what is left for you is to evaluate $$\chi^T{\bf{A}}\chi$$ and $$\chi^T\chi$$.