Exercise 6.16: Graphs and Adjacency Matrices
Define \(\tau \subset \N\) to be the set of indices associated with members of an \(s\)-clique, \(v^\top A v = s\) for \(v_i = \frac{\ind_{i \in \tau}}{\sqrt{s}}\), implying \(\|A\|_2 \geq s\).
For the upper bound, take \(v\) to an eigenvector such that \(\| A v \|_2 = \| A \|_2\), and \(i\) to be an index for which \(|v_i| = \| v \|_\infty\). Then \begin{align} \| A \|_2 |v_i| = | [A v]_i | \leq \| A v \|_\infty \leq \| A \|_\infty |v_i| \, . \end{align} Since \(v \neq 0\), the above implies \(\| A \|_2 \leq \| A \|_\infty\). We conclude by observing \(\| A \|_\infty = \max_i \| A_{i \cdot} \| = s\) which follows by the assumed maximum degree \(s - 1\) (remember \(A\) is defined with ones on the diagonal here).