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

Question

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.

Answer 1

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$.