Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 2 down vote accepted

I'll use the more usual term for what you call a "perfect graph", namely "complete graph".

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.