Let G be a graph with at most two distinct Eigenvalues. Show that G is Complete.

Question

Here Eigenvalues of a Complete graph it is said that a complete graph has eigenvalue n-1 with multiplicity 1 and eigenvalue -1 with multiplicity n-1. I have seen in all examples that I could come up with that a graph with at most two distinct Eigenvalues is complete. Is there a general proof for the same?

Answer 1

If the graph has only two eigenvalues, the minimal polynomial of its adjacency matrix is $t^2+at+b$ for some $a$ and $b$. If $a=0$, then $A^2=-bI$ and the only 01-matrix that satisfies this is $I$ itself. So \[ A^2 = -aA -bI \] and therefore if $u\ne v$ and $(A^2)_{u,v}\ne0$, then $A_{u,v}\ne0$. In other words if two vertices in the graph are distance two they are adjacent. It follows that a connected graph with only two eigenvalues is complete.

Note that two vertex-disjoint copies of $K_n$ is a graph with only two eigenvalues.