# On the eigenvalues of “almost” complete graph ?!

Preliminaries:
Let $K_n$ be the complete graph on $n$ vertices. $|E(K_n)|=\frac{n(n-1)}{2}$.
It's well known that the eigenvalues of $K_n$ are $n-1$ with multiplicity 1, and -1 with multiplicity $n-1$.

Let $E'=\{e_1,\ldots,e_l\}\subset E(K_n)$, where $l\leq \frac{n}{2}$
Let $G'$ be the graph obtain from $K_n$ in the following way:
-$V(G')=V(K_n)$
-$E(G')=E(K_n)-\{E'\}$
That means $G'$ is the graph obtained from $K_n$ by removing "relatively" small number of edges.

Question?
Is it possible to commute the spectrum of $G'$ if $E'$ satisfies certain conditions? for example one of the following:
-$E'$ is perfect matching of $K_n$
-$|E'|\leq 4$.
Is there any work in this direction?

Ideas:
-Since -1 is eigenvalue of $K_n$ with very high multiplicity (that is $n-1$), then I guess that by removing small number of edges from $K_n$, -1 will still be eigenvalue with high multiplicity -Interlacing theorem could help in commutating the eigenvalues of $G'$.

Any idea will be useful!

Let $N(x)$ denote the neighbourhood of the vertex $x$ in the graph $G$ and suppose that $u$ and $v$ are distinct vertices of $G$ such that ${u} \cup N(u) = {v} \cup N(v).$ (We say that $u$ and $v$ have same closed neighbourhoods.) Let $f$ the vector indexed by $E(G)$ such that $f_u=1$ and $f_v=-1$ and $f_x=0$ if $x\ne u,v$. You may check that $f$ is an eigenvector of $A(G)$ with eigenvalue $-1$. If there are $k$ vertices such that any two have same closed neighbourhood, you may show that $-1$ is an eigenvalue with multiplicity at least $k-1$.
• Could you give me hint why the multiplicity of $-1$ is $k-1$? Please tell me if this is correct: Suppose that $N(u)=N(v)$ and let $f$ be the same vertor you described, then $f$ is eigenvector of $A(G)$ with eigenvector $0$. If there are $k$ vertices such that any two vertex have the same neighbour, then $0$ is an eigenvalue with multiplicity $k-1$. – M.Badaoui Apr 20 '16 at 13:56
• @M.Badoui: Fix one vertex, call it $u$. For each vertex $v$ with the same closed neighborhood as $u$, construct an eigenvector $F_v$ as above. This gives us $k-1$ eigenvectors, each of which has only two non-zero entries. Since one of these non-zero entries is index by $u$, it's not hard to show that our $k-1$ vectors are linearly independent. – Chris Godsil Apr 20 '16 at 20:12