I am stuck at the following :


Let $G$ be a graph and $A$ is its adjacency matrix.
Let the eigenvalues of $A$ be $\lambda\_1\le \lambda\_2\leq \cdots \leq \lambda\_n$.


If we remove some edges from the graph $G$ and form the graph $H$ keeping the number of vertices same, is there any result how the smallest eigenvalue of $H$ is related to the smallest eigenvalue of $G$?


I know Cauchy Interlacing Theorem which gives the relation between eigenvalues of a graph and its induced subgraph when some vertices are removed.


I want to know what happens when edges are removed keeping the number of vertices same. Can someone help please?


The question stands as:


Let $G$ be a graph and $A\_G$ is its adjacency matrix.
Let the eigenvalues of $A\_G$ be $\lambda\_1\le \lambda\_2\leq \cdots \leq \lambda\_n$.


Let $H$ be a subgraph of $G$ which has $n$ vertices as $G$ but some edges have been removed from $G$ to form $H$.$A\_H$ is its adjacency matrix.


Let the eigenvalues of $A\_H$ be $\mu\_1\le \mu\_2\leq \cdots \leq \mu\_n$.


Is $\mu\_1\ge \lambda\_1$ or $\mu\_1\le \lambda\_1$?


If someone can give any reference like book or paper , I will be grateful.



What happens to eigenvalues when edges are removed?
The smallest eigenvalue can go up or down when an edge is removed.


For "down": $G=K\_n$ for $n\ge 3$.


For "up": Take $K\_n$ for $n\ge 1$ and append a new vertex attached to a single vertex of the original $n$ vertices. Now removing the new edge makes the smallest eigenvalue go up.


Both of these follow from the fact that the smallest eigenvalue of a connected graph with $n\ge 2$ vertices is $\le -1$ with equality iff the graph is complete.


It has something to do with whether the two corresponding eigenvector entries have the same or opposite sign, but I don't know if that relationship can be made precise.


