I understand how to prove a complete graph $K_n$ has spectrum $\lbrace -1^{(n-1)},n-1 \rbrace$. However I am having difficulty proving that the spectrum uniquely determines the complete graph.
Wolfram seems to suggest there is a simple proof, http://mathworld.wolfram.com/DeterminedbySpectrum.html .
Any ideas how to construct all graphs from these eigenvalues or prove this construction indirectly?
The adjacency matrix of a complete graph is $J-I$ such that $J_{ij}=1$ for all $i,j$. Since J is symetric it has an orthonormal basis of eigenvectors (ie diagonalisable in an orthonormal basis), and being of rank 1 (all columns are the same), it has 0 as eigenvalue of order (n-1), and the trace which is n of order 1.
Then $J-I$ being a polynomial in J, the eigenvalues are the images of $J$'s eigenvalues, hence -1 of order n-1 and n-1 of order 1.
Conversely, if you have the previous spectrum, then the adjacency matrix of the graph G is such that there exists $O$ orthonormal matrix such that $W = O^T J O - I$. $W$ being an adjacency matrix, it is a zero-one matrix. Hence, if we write $v_i = \sum_k O_{ki}$, we have for all $i,j$ : $$(v_i)^2 = 1, v_iv_j\in\{0,1\}$$ The $v_i$ have the same sign, you can assume positive or take $-O$. Then $v_i = 1$ for all $i$ and the graph is complete