prove that $\Delta(G)\leq \lambda_{max}^2$ Let $G$ be a graph and let $\lambda$ be its largest eigenvalue. Prove that
$$\Delta(G)\leq \lambda^2$$
where $\Delta(G)$ is the maximum degree of vertices of $G$.
I've seen this problem being regarded as a well-known fact in this post, but I can not prove it or find it in any algebraic graph theory books. Any hints or solutions are appreciated.
 A: I'm sure there's a more elementary proof, but here's one way.
Let $G = (V,E)$ be our graph, with $V = \{u_1, \dots, u_n\}$ and adjacency matrix $A = A(G)$. It'll be helpful to think of a vector $\vec{y} = (y_1, \dots, y_n)$ as a function $f : V\to \mathbb{R}$ that assigns the value $y_i$ to vertex $u_i$.
We'll assume that $G$ is connected. By the Perron-Frobenius Theorem for non-negative matrices, we get that the largest eigen-value $\lambda$ has a corresponding eigen-vector $\vec{x} = (x_1, \dots, x_n)$ where every entry $x_i$ is positive.
Let $u_j$ be a vertex such that $\deg(u_j) = \Delta$. By scaling our positive eigen-vector $\vec{x}$ by a positive constant, we may assume without loss of generality that:
$$ \min\{x_i : u_i \in N(u_j)\} = 1$$
Now consider what happens when we apply $A$ to $\vec{x}$. We know $A\vec{x} = \lambda \vec{x}$. We also know that the $j^{th}$ component of $A\vec{x}$ is obtained by summing up all the entries $x_i$ of $\vec{x}$, where the vertex $u_i$ is adjacent to $u_j$. In short:
$$ \lambda x_j = (A\vec{x})_j = \sum_{u_i\in N(u_j)}x_i$$
Since $\min\{a x_i : u_i \in N(u_j)\} = 1$ by assumption, we get:
$$\Delta = \sum_{u_i\in N(u_j)}1 \leq \sum_{u_i\in N(u_j)}x_i = \lambda x_j$$
So $\Delta = \lambda x_j$.
By our assumption again, there exists a neighbour $u_k$ of $u_j$ such that $x_k = 1$. Applying $A$ to $\vec{x}$, we get
$$ \lambda (1) = \lambda x_k = (A\vec{x})_k = \sum_{u_i\in N(u_k)}x_i $$
All the terms in the sum on the right are positive (since $\vec{x}$ is our Perron Frobenius eigenvector), and $x_j$ is one of those terms. Therefore we have that $x_j \leq \lambda$.
Putting this all together, we have $\Delta \leq \lambda x_j \leq \lambda^2$.
