Here's a very elementary example. Let G be a graph with adjacency matrix A. Then the number of distinct triangles in G is equal to
tr(A³)/6
where tr() is the trace.
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.
Edited 24d ago
@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.
@robinhouston I don't know what “counts”, I know very little about any of it.
@mjd I've been intermittently curious, but never got deep into any aspect of it except the matrix-tree stuff.