I don't know if I am the only one that feels this, but damn Spectral Graph Theory needs some notation change... Maybe it is because I am not so experienced in the field yet, but man every time I read a result on eigenvalues I am not certain to what spectrum it refers to.
This lemma here is one such case. I wrote it down as a useful tool at some point in the past and now I can't remember whether it holds for adjacency matrix spectrum or Laplacian! :( Can anyone help? Here is the result:
Lemma 1: Let $G$ be a connected graph and let $H$ be a proper connected subgraph of $G$. Then $\lambda(H) < \lambda(G)$.
Proof. Notice that it suffices to prove this for the case that $E_G = E_H +1$. Let $v \in H$ be a vertex incident to the extra edge, let $a_{n, v}$ be the number of closed walks in $H$ from $v$ to itself of length $n$, and let $b_{n, v}$ be the number of closed walks in $G$ from $v$ to itself of length $n$. By the previous lemma (I have this lemma as well, but it did not give me any insight, if you need it let me know), it suffices to show that $\frac{b_{n, v}}{a_{n, v}}$ can be made arbitrarily large for large $n$.
Choose $n$ much larger than some fixed constant $C$. Notice that among the paths from $v$ to itself in $G$ of length $2n$ there are paths which travel from $v$ to itself in $H$ for $n-k-1$ steps, traverse the extra edge in $G$ and back again, and then travel from $v$ to itself in $H$ for the remaining $n+k-1$ steps, for every $k \in[-C,C].$ It follows that
$$ b_{2n,v} \geq \sum_{k=-C}^C a_{n-k-1, v}\cdot a_{n+k-1, v} $$
Taking $C$ to be sufficiently large, the result follows. $\qed$
Thanks in advance for any help guys, it is really needed! :|
Since you're using closed walks, it will be the spectrum of the adjacency matrix. (But it's hard to e absolutely certain, since you have not defined $\lambda(G)$.) And you do not need $H$ to be connected.