Show that the largest eigenvalue of a graph is strictly larger than the largest eigenvalue of any subgraph

Question

Let G be a connected graph and H be any proper subgraph of G (obtained from removing at least one edge or at least one vertex of G). Show that the largest eigenvalue of A(G) is strictly larger than the larger eigenvalue of A(H).

The eigenvalues in question are the eigenvalues for the adjacency matrixes. I tried reasoning that by removing edges/vertices we are turning indexes into $0$, but it doesn't seem to lead anywhere.

Answer 1

One way to identify the largest eigenvalue of a symmetric matrix $A$ is by the following characterization: it is the maximum of $\mathbf x^{\mathsf T}\!A\mathbf x$ over all $\mathbf x$ with $\|\mathbf x\|=1$, and moreover, the maximum can be achieved by letting $\mathbf x$ be the corresponding eigenvector. To see this, write $\mathbf x = c_1 \mathbf v^{(1)} + \dots + c_n \mathbf v^{(n)}$ in the basis of orthonormal eigenvectors of $A$. Then $c_1^2 + \dots + c_n^2 = 1$ and $\mathbf x^{\mathsf T}\!A\mathbf x = \lambda_1 c_1^2 + \dots + \lambda_n c_n^2$. If $\lambda_n$ is the largest eigenvalue, this is maximized by setting $c_n = \pm1$ and all other $c_i$ to $0$.

Moreover, when $A$ is nonnegative, as it is here, then $\lambda_n$ has a nonnegative eigenvector. To see this, note that if we replace each component $x_i$ of $\mathbf x$ by $|x_i|$, then the value of $\mathbf x^{\mathsf T}\!A\mathbf x$ can only increase.

---

Now, on to the graph theory.

We can always assume $H$ has the same number of vertices as $G$; if it's a subgraph with fewer vertices, add some isolated vertices to pad it out (which will only contribute some zero rows). Let $\lambda_n(G), \lambda_n(H)$ be the largest eigenvalues of the adjacency matrices $A_G, A_H$, and let $\mathbf w$ be a nonnegative unit eigenvector of $A_H$ corresponding to $\lambda_n(H)$. Then $$ \lambda_n(H) = \sup_{\mathbf x \in \mathbb R^n : \|\mathbf x\|=1} \mathbf x^{\mathsf T}\!A_H\mathbf x = \mathbf w^{\mathsf T}\!A_H\mathbf w \le \mathbf w^{\mathsf T}\!A_G\mathbf w \le \sup_{\mathbf x \in \mathbb R^n : \|\mathbf x\|=1} \mathbf x^{\mathsf T}\!A_G\mathbf x = \lambda_n(G) $$ where the middle inequality holds because whenever we increase some $(i,j)$-th entry of $A_H$ from $0$ to $1$, it gets multiplied by the nonnegative quantity $w_i w_j$.

The strictness of the inequality can come from one of two places. First notice that if $\mathbf w$ is an eigenvector of $A_H$, then $\lambda_n(H)w_i$ is the sum of $w_j$ over all vertices $j$ adjacent to $i$. So if $w_i$ is $0$, then $w_j=0$ for all $j$ adjacent to $i$, which means that $\mathbf w$ vanishes on the entire connected component connecting $i$. So:

• If $H$ is connected as well as $G$, then all entries of $\mathbf w$ are positive, so there must be a strict increase going from $\mathbf w^{\mathsf T}\!A_H\mathbf w$ to $\mathbf w^{\mathsf T}\!A_G\mathbf w$. The first $\le$ is $<$.
• If $H$ is not connected, then we may assume $\mathbf w$ vanishes on all but one of the connected components. But then $\mathbf w$ is definitely not an eigenvector of $A_G$: going from $G$ to $H$, we'll end up adding an edge out of that connected component, which will propagate nonzero values of $A_G\mathbf w$ to vertices where $\mathbf w$ vanished. The second $\le$ is $<$ (because it can only be $=$ for an eigenvector of $\lambda_n(G)$).