1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

By the Perron–Frobenius theorem, the largest eigenvalue of a nonzero adjacency matrix is positive, and has an eigenvector with nonnegative components to go along with it.

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 the eigenvector of $A_H$ corresponding to $\lambda_n(H)$. We use a fact from linear algebra: for a matrix $A$, $\frac{\mathbf x^{\mathsf T}\!A\mathbf x}{\mathbf x^{\mathsf T}\mathbf x}$ is maximized only by setting $\mathbf x$ equal to an eigenvector of the largest eigenvalue of $A$, when the fraction simplifies to that eigenvalue. Therefore $$ \lambda_n(H) = \sup_{\mathbf x \in \mathbb R^n-\{\mathbf 0\}} \left\{\frac{\mathbf x^{\mathsf T}\!A_H\mathbf x}{\mathbf x^{\mathsf T}\mathbf x}\right\} = \frac{\mathbf w^{\mathsf T}\!A_H\mathbf w}{\mathbf w^{\mathsf T}\mathbf w} \le \frac{\mathbf w^{\mathsf T}\!A_G\mathbf w}{\mathbf w^{\mathsf T}\mathbf w} \le \sup_{\mathbf x \in \mathbb R^n-\{\mathbf 0\}} \left\{\frac{\mathbf x^{\mathsf T}\!A_G\mathbf x}{\mathbf x^{\mathsf T}\mathbf x}\right\} = \lambda_n(G) $$ where the middle inequality holds because whenever we increase the $(i,j)$-th entry of $A_H$, 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_G$, 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)$).
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.