It is possible to bound the number of connected components of the positive and negative supports of an eigenvector of a graph.
Proof: For a subset of the vertex set of , let be the diagonal matrix with ones on the positions indexed by elements of and zeros elsewhere.
Let run through the connected components of and . Put . Then the space has dimension .
For simplicity, replace by the adjacency matrix of , and then replace by . Define a real symmetric matrix by . Then has zero row sums and nonpositive off-diagonal entries, so is positive semidefinite and by Lemma 1.13.2 the number of zero eigenvalues equals . It follows that for we have . This means that intersects the space spanned by the eigenvectors with negative eigenvalue in 0, and follows. The vectors with correspond to eigenvectors with eigenvalue 0 of , and altogether there are independent such. This proves the other inequality.
Examples (i) Let be connected and bipartite, and let be the smallest eigenvalue of . The corresponding eigenvector has different signs on the two sides of the bipartition, so and are the two sides of the bipartition, is the total number of vertices and . We have equality in both inequalities.
(ii) Let be the star . The spectrum is , , . Let be an eigenvector with eigenvalue . We can choose to be nonzero off the apex of the star. Then and , , again equality in both inequalities.
(iii) Let be the Petersen graph. It has spectrum , , . Let be an eigenvector with eigenvalue that vanishes on 4 points, so that induces with spectrum , . We find and , , again equality in both inequalities.
(iv) Let be the path of length (with vertices). The eigenvalues are for . The eigenvector corresponding to has sign changes, so that . If then has no zero entries, so that . Now we have equality in both inequalities. If , then has zero entries, so that . Also, the eigenvalue is the -th of each component of , so that and , again with equality in both inequalities.
Remark By interlacing, the numbers and for are upper bounded by the corresponding numbers for , but it is not true that . For example, in case (ii) above we have but the multiplicity of in the spectrum of is .