It is possible to see from the spectrum whether a graph is regular:
Proof: We have seen that (i) and (ii) are equivalent. Also, if is regular of degree , then . Conversely, if (iii) holds, then and by the above is regular.
It is also possible to see from the spectrum whether a graph is regular and connected:
But one cannot see from the spectrum alone whether a graph is connected:
Both and have spectrum
, , (where multiplicities are written as exponents).
And both and have spectrum
, , , , .
Another very useful characterization of regular connected graphs was given by Hoffman :
Proof: If , then commutes with and hence is regular (and clearly also connected). Conversely, let be connected and regular. Choose a basis such that the commuting matrices and become diagonal. Then becomes and becomes . Hence, if we put , then , so that satisfies the requirements.