# Proofs obtained only through spectral graph theory

I have an increasing interest in spectral graph theory, which I find fascinating, and I've started collecting a few documents that I have yet to read more thoroughly than what I so far have.

However, I'm curious about a statement that popped up in several sources (for instance over there), which says in essence that some results in graph theory have been proved using spectrum-based techniques only, and that so far, no proof that bypasses those techniques is known.

Unless I skipped that, I don't recall seeing such an example in the literature I've read so far. Do any of you know of examples of such results?

• The title of the question suggests that you are asking for proofs that are only obtainable using spectral graph theory, but you are asking for proofs that have up to now only been obtained by spectral graph theory. These are two totally different questions. So as it stands, the title is misleading, which is why I changed it. Feb 23 '11 at 16:18
• @Dave I did a rollback Feb 23 '11 at 17:15
• Chapter 7 of Spectra of Graphs by Cvetković, Doob, and Sachs gives plenty of examples of theorems whose statements make no explicit mention of spectra but that are provable using spectral techniques. My guess is that many of these have no known non-spectral proof, though you'd have to verify this on a case-by-case basis. Certainly in many cases the simplest or most natural proof uses spectra. Feb 24 '11 at 23:57
• @Timothy Chow: Thanks, I'll try to get my hands on it. Feb 25 '11 at 6:49
• @TimothyChow: You should make this an answer, I think. Feb 25 '11 at 7:45

• Hoffman-Singleton was my first thought, too. But, I don't know if any non-spectral proofs exist and if they don't if it's because they're too difficult or because no one has tried. The standard proof is pretty neat and concise, so I don't know offhand what the motivation would be to get a non-spectral proof.
– mhum
Feb 23 '11 at 23:57

I think that the friendship theorem (see also Huneke's paper) is a good example even though strictly speaking there now exist proofs of the friendship theorem that avoid eigenvalues. The proofs that avoid eigenvalues entirely are a lot messier than the spectral proof.

(The friendship theorem states that if in a room of people, every pair of people has exactly one common friend, then there is someone who knows everyone else.)

Let $L_G$ be the Laplacian matrix of an undirected weighted graph $G = (V,E,w)$. A sparsifier of a graph $G$ is a graph $H$ such that for every $x \in R^V$ the following holds: $$x^T L_H x (1-\epsilon) \le x^T L_G x \le x^T L_H x (1+\epsilon).$$ Using spectral methods, Batson et al. show how to construct these sparisifiers using $O(n/\epsilon^2)$ edges.
• This is kind of a spectral statement. $F(A) = \{x^TAx: ||x||_2 = 1\}$ is exactly the convex hull of the eigenvalues of A if A is the Laplacian of an undirected graph. The condition is asking for another graph with approximately the same spectrum. But I think it is not even known how to get plain old cut sparsifiers with $O(n/\epsilon^2)$ edges in another way. May 5 '11 at 20:10