(i) is at most the number of nonnegative (nonpositive) eigenvalues of .
(iii) If is regular, then .
(iv) If is strongly regular, then .
Proof: (i) This follows by interlacing.
(ii) Suppose has a proper colouring with colours. Let be the diagonal matrices with ones on the diagonal for the positions of the -th colour class and zeroes elsewhere. Then . Let be an eigenvector for the eigenvalue of , and put . Then so that .
Suppose is regular of degree and has a coclique of size .
The corresponding partition of the vertex set in two parts gives a matrix of
average row sums
(iv) We have . When is strongly regular we have and and (with standard notation , ) (because both sides coincide on the eigenvectors for and , so the left hand side is a multiple of , but it is on the diagonal), so that , and the claim follows from part (iii).
Remark The proof of (ii) only uses that vanishes where has a nonedge; may have arbitrary values on edges.
Example The strongly regular Higman-Sims graph has parameters and eigenvalues of multiplicities , respectively. Each point neighbourhood is a coclique of size 22, and we have equality in (i).