What are some subtle, or non-obvious applications of algebraic graph theory? Obviously it can be used to study anything directly involving graphs (for instance, the wikipedia page mentions synchronizability of networks), but I'm interested in places where one might not immediately think graph theory to be relevant.
It is more likely to find subtle, nonobvious applications of algebraic graph theory to graph theory.
A celebrated early example is the Friendship Theorem
which has a nice proof using the spectrum of the adjacency matrix.
More recently the critical groups of sandpiles on graphs are a major theory related to tropical geometry. There are strong analogies with Riemann-Roch theory of divisors on algebraic curves.
Graph Laplacians are of huge interest, and closely related to the previous example.
Spectral embedding of graphs in the plane is another nice use of the adjacency matrix.
In applications outside graph theory, the structure of a graph relevant to the problem is usually not a well-hidden fact. If you are looking for applications of algebraic graph theory to generally obvious graph structure such as chemical bonds, there is plenty of that.
One application of algebraic graph theory is the design and analysis of topologies of interconnection networks. The topologies that are used to connect processors in a supercomputer have a high degree of symmetry and are usually Cayley graphs. See the Wikipedia article on the Torus interconnect, a topology used in some of the supercomputers.