Algebraic Graph Theory - Bounding Spectral Radius

Question

If $X$ is a graph with maximum valency $a$, show that $\sqrt{a} \leq \rho(A(X)) \leq a$.(From Algebraic Graph Theory by Godsil & Royle.)

I think I have to use the Rayleigh quotient to prove the bounds somehow but I'm not sure exactly how.

Answer 1

For one direction: let $\|\cdot \|_\infty$ denote the induced $\infty$-norm, which satisfies $$ \|A\|_\infty = \max_{i=1,\dots,n} \sum_{j=1}^n |A_{ij}|. $$ We note that the $i$th row sum is equal to the degree of the $i$th vertex, so that $\|A\|_\infty = a$. However, it generally holds that $\|A\|_\infty \geq \rho(A)$. Thus, we have $\rho(A) \leq \|A\|_\infty = a$.

For the other direction: suppose without loss of generality that the first vertex of $X$ has degree $a$. Let $x$ denote the vector whose entries are given by $$ x_j = \begin{cases} 1 & j=1 \text{ or } 1 \sim j\\ 0 & \text{otherwise}. \end{cases} $$ We see that $\|x\| = \sqrt{a}$. On the other hand, we note that $Ax$ has $a$ as its first entry, so that $\|Ax\| \geq a$. We note that because $A$ is symmetric, its spectral norm is equal to its spectral radius so that $$ \rho(A) = \max_{y \in \Bbb R^n} \frac{\|Ay\|}{\|y\|} \geq \frac{\|Ax\|}{\|x\|} \geq \frac{a}{\sqrt{a}} = \sqrt{a}. $$