If $G$ is a simple graph with adjacency matrix $A$ then the following inequalities are known to hold (See eg. Prop 2.1. of this note of Lovász – there's no proof given though):
$$\sqrt{\Delta(G)}, d_{\text{avg}}(G) \leq \lambda_{\text{max}}(A) \leq \Delta(G)$$
Where $\Delta(G)$ denotes the maximum degree of $G$ and $d_{\text{avg}}(G)$ denotes the average degree.
Would any of the two lower bounds hold if we considered instead an edge weighted graph $G$? If necessary, the weights can be assumed to be non-negative. I have been looking at some textbooks but I couldn't even found a proof of the lower bound $\sqrt{\Delta(G)}\leq \lambda_{\text{max}}(G)$.
Best Answer
One way to prove lower bounds on $\lambda_\max$ is with the Rayleigh quotient: we find a vector $\mathbf x$ such that the quotient $q = \frac{\mathbf x^{\mathsf T}\!A \mathbf x}{\mathbf x^{\mathsf T}\mathbf x}$ is large, and conclude that $\lambda_\max(A) \ge q$.
The denominator is always $x_1^2 + \dots + x_n^2$. If $A$ is the adjacency matrix of a graph, then the numerator has a term $2x_i x_j$ whenever vertices $i$ and $j$ are adjacent.
Suppose that vertex $i$ in our graph has degree $d$. Define $x$ as follows: set $x_i = \sqrt d$, set $x_j = 1$ whenever $i$ and $j$ are adjacent, and set all other components of $\mathbf x$ to $0$. Then $\mathbf x^{\mathsf T}\!A \mathbf x$ has $d$ nonzero terms: the terms $2x_i x_j$ wherever whenever $j$ is a neighbor of the vertex $i$ chosen above. Each term is equal to $2\sqrt d$, so the numerator is $2d\sqrt d$. The denominator is equal to $1 \cdot (\sqrt d)^2 + d \cdot 1^2 = 2d$, and the quotient of these is $\sqrt d$. Therefore $\lambda_\max(A) \ge \sqrt d$; taking $i$ to have the maximum degree, we conclude that $\lambda_\max(A) \ge \sqrt{\Delta(G)}$.
Another way of thinking about this: $\lambda_\max$ of any graph $G$ is no less than $\lambda_\max$ of any subgraph $H$. This is proven by exactly the Rayleigh quotient argument. If we know that $\Delta(G) = d$, then we know that $G$ contains the subgraph $K_{1,d}$, whose maximum eigenvalue is $\sqrt d$; therefore $\lambda_\max(G) \ge \sqrt d$ as well.
The appropriate generalization to weighted graphs involves finding the maximum eigenvalue of a weighted star $K_{1,d}$. This turns out to be $\sqrt{w_1^2 + w_2^2 + \dots + w_d^2}$, where $w_1,\dots, w_d$ are the weights of the $d$ edges.
So to prove the correct lower bound for an arbitrary graph $G$, suppose that vertex $0$ in our graph has neighbors $1, 2, \dots, d$ and weights $w_1, w_2, \dots, w_d$ on the edges to them. Let $w = w_1^2 + w_2^2 + \dots + w_d^2$: this will be our generalization of the degree of $0$ for the time being.
Set $x_0 = 1$, set $x_j = \frac{w_j}{\sqrt w}$ for $j=1, \dots, d$, and set all other components of $x$ to $0$. The numerator of the Rayleigh quotient has a term $2w_j x_0 x_j = 2w_j^2/\sqrt w$ for $j=1, \dots, d$, and their sum is just $2\sqrt w$. The denominator is $1 + \sum_{j=1}^d \frac{w_j^2}{w}$, which simplifies to $2$. So we prove a lower bound of $\sqrt w$ on $\lambda_\max$.
Therefore in a weighted graph, the corresponding lower bound to $\sqrt{\Delta(G)}$ is the square root of the maximum sum of squared weights of incident edges over all vertices of $G$.