Here are a couple of interesting results from spectral graph theory. Let G be a connected graph and A be its adjacency matrix.

1. G is bipartite if and only if the eigenvalues of A are symmetric about 0.

2. Let D be the maximum degree of a vertex of G. Then G is regular if and only if D is an eigenvalue of A.

3. If A has N distinct eigenvalues, then the diameter of G is strictly less than N.

@mjd Does it count as spectral graph theory if you consider the Laplacian matrix of the graph, rather than its adjacency matrix? Because I think the matrix-tree theorem is very deep and interesting.

@mjd I've been intermittently curious, but never got deep into any aspect of it except the matrix-tree stuff.