# Eigenvalues of a connected graph $G$ are greater than or equal to $-1$ iff $G$ is perfect?

Consider $P_G$ as the characteristic polynomial of the adjacency matrix of the connected graph $G$.
It is easy to prove that $P_{K_n}(x)=(x-n+1)(x+1)^{n-1}$, so all of the eigenvalues of a perfect graph is greater than or equal to $-1$. Now we need to prove the inverse that if all of the eigenvalues of $G$ were not less than $-1$ then $G$ must be perfect.

-
I think you're missing a hypothesis that $G$ is connected. The graph without edges has all eigenvalues $0$, and any graph whose connected components are all perfect graphs has eigenvalues not less than $-1$, since they're given by the eigenvalues of the connected components. –  joriki Feb 18 '13 at 22:21
What have you tried? –  user67258 Apr 15 '13 at 4:16

It doesn't follow that $G$ is complete, only that every connected component of $G$ is complete. Alternatively, it follows that $G$ is complete if you add the hypothesis that $G$ is connected.
To see this, take any edge in $G$ and consider the vector $v$ with entry $-1$ at one vertex of the edge, $+1$ at the other and $0$ otherwise. The value $v^\top Av$ of the quadratic form defined by the adjacency matrix $A$ of $G$ is $-2=-\lVert v\rVert$, so either $v$ is a linear combination of eigenvectors with eigenvalues greater and lesser than $-1$, or it's an eigenvector with eigenvalue $-1$. In the former case we're done, and in the latter case it follows that the two vertices of the edge have the same neighbours (otherwise $Av$ would have non-zero entries where $v$ has zeros), and the same follows for the neighbours' neighbours, and hence the connected component containing the vertices is complete.