intuition - Spectral graph theory: Interpretability of eigenvalues and -vectors

Interesting structural features in graphs are often reflected in eigenvectors (how's that for a generality?) It is often a matter of skill which eigenvector to take. For example, a cyclic grph has multiplicity 2 for the next to largest eigenvalue. Take a 6-cycle (since it is easy). The 2nd eigenvalue is 1 and a generic eigenvector (in cyclic order) is
(1,t,t-1,-1,-t,1-t) SO (looking for relatively few distinct values)
(1,1/2,-1/2,-1,-1/2,1/2) and (1,1,0,-1,-1,0) (and their cyclic shifts) seem nice. Rotating the latter to (0,1,1,0,-1,-1) multiplying by $frac{sqrt{-3}}{2}$ and adding this to (1,1/2,-1/2,-1,-1/2,1/2) does give a nice eigenvector with values on the unit circle, but it is not the eigenvector.

Here is another way to see that $-lambda$ is an eigenvalue of a bipartite graph when $lambda $ is: Take an eigenvector for $lambda$ and replace all the values in one part by their negatives. This shows that (since the largest eigenvalue is unique in that it has an all positive eigenvector) the smallest (in the bipartite case) is unique in that it is positive on one half of the graph and negative on the other, so it reveals the bipartition. One might guess that in a general graph the smallest eigenvalue might have some eigenvectors which partition the vertices into two classes (positive and negative) in a way which minimizes the number of edges connected vertices of the same sign. Several theorems of Miroslav Fiedler are relevant to these considerations.

I'll mention too that I've found it useful to consider the subspace spanned by (eigenvectors for) several eigenvalues. Consider the skeleton of a cube. The sum of the first and second eigenspaces are spanned by the characteristic vectors of the 6 faces. The sum of the first second and third eigenvalues is spanned by the characteristic vectors of the 12 edges. The sum of the first four eigenvalues (i.e. everything!) is spanned by the characteristic vectors of the 8 vertices. This is true (mutatis mutandis) much more generally (Hamming graphs, finite nets, Johnson graphs and other graphs arising from highly regular geometries).