# Difference of the maximum eigenvalue of a graph with the one of one-edge-deleted subgraph

Let $G$ be a graph and $e$ be an edge of the graph $G$ such that the subgraph $G\setminus e$ is connected. The subgraph $G\setminus e$ is the subgraph of $G$ obtained by deletion of the edge $e$ of $G$. Assume that $G$ has $n$ vertices. Is it true that $\lambda(G)-\lambda(G\setminus e)\geq \frac{1}{n}$? Here $\lambda(G)$ denotes the maximum eigenvalue of adjacency matrix of $G$.

-

It's always useful to test these questions on actual examples. The largest eigenvalue of the cycle $C_n$ is 2 and the largest eigenvalue of the path $P_n$ on $n$ vertices is $2\cos(\pi/(n+1))$. When $n=8$, this is 1.879385 and $2-1.8793852=0.120615 <1/8$.

In fact it is not hard to see that for large $n$ the difference $2-2\cos(\pi/(n+1))$ is of order $\pi^2/(n+1)^2$, and so your lower bound is not even of the right order.

-
@Chris. Many Thanks. – Alireza Abdollahi Dec 18 '12 at 4:04

This conjecture is not true in general. For example, let $G$ be a graph that obtained from joining the end vertex of $P_3$, $P_3$ and $P_4$, where it is an star-like tree. This graph has largest eigenvalue equal to $2.02852$. Now join the end vertex of $P_4$ to the end vertex of $P_3$. Therefore we added an edge to the previous graph. The largest eigenvalue of this graph is $2.13578$. Then the difference of this values is $0.10726$. But this graph has $8$ vertices and $1/8=0.125$. It is a counter example.

Also, we can construct a family of star-like tree that does not have this property. Also, I think for any polynomial $f(n)$, we can construct a graph $G$ such that $\lambda(G)-\lambda(G-e)\geq \frac{1}{f(n)}$ is not true.

-
@Shahrooz. Many thanks. – Alireza Abdollahi Dec 18 '12 at 4:04