In Which graphs are determined by their spectrum? proposition 6 states "the disjoint union of complete graphs is DS, with respect to adjacency matrix." A graph is said to be DS (determined by its spectrum) if its spectrum uniquely determines its isomorphism class. I read the proof and I was confused.
I searched about it. I found this: On NP-hard graph properties characterized by the spectrum. In lemma 1, there is the same result. To prove the lemma, it's stated: "... a graph $G$ (with at least one edge) is the disjoint union of cliques if and only if $G$ has smallest eigenvalue $−1$. But we can say more. If the smallest eigenvalue is $−1$, then every other eigenvalue $\lambda$ is a nonnegative integer, and corresponds to a clique of order $\lambda+1$." It seems it's easier but I can't prove it.
Thanks for your help.
A graph is the disjoint union of cliques if and only if the graph does not contain a $3$-vertex path as an induced subgraph: if, whenever $uv \in E$ and $vw \in E$, we also have $uw \in E$.
Induced subgraph characterizations help us understand eigenvalues (and vice versa) because of the eigenvalue interlacing theorem. This says that if $A$ is a symmetric matrix (like, say, a graph's adjacency matrix) with eigenvalues $\alpha_1 \le \dots \le \alpha_n$, and $B$ is a principal submatrix of $A$ (like, say, the adjacency matrix of an induced subgraph) with eigenvalues $\beta_1 \le \dots \le \beta_k$, then $$ \alpha_i \le \beta_i \qquad\text{and}\qquad \beta_{k+1-i} \le \alpha_{n+1-i} $$ for $i=1, \dots, k$. (The $i^{\text{th}}$ smallest eigenvalue of $A$ is smaller than the $i^{\text{th}}$ smallest eigenvalue of $B$, and the $i^{\text{th}}$ largest eigenvalue of $A$ is larger than the $i^{\text{th}}$ largest eigenvalue of $B$.)
In our case, the $3$-vertex path $P_3$ has eigenvalues $-\sqrt2 \le 0 \le \sqrt2$. Therefore if a graph has a $3$-vertex path as an induced subgraph, its smallest eigenvalue is $-\sqrt2$ or less. The only graphs that can have a smallest eigenvalue of $-1$ are disjoint unions of cliques. (We haven't proven that they have this property yet - just that nothing else can.)
The eigenvalues of $K_n$ are $n-1$ (with multiplicity $1$) and $-1$ (with multiplicity $n-1$). When we take disjoint unions, we just combine all the eigenvalues. Therefore, the eigenvalues of $K_{n_1} \cup \dots \cup K_{n_t}$ are $n_1-1, \dots, n_t -1$ (with multiplicity $1$) and $-1$ (with multiplicity $n_1 + \dots + n_t - t$).
If $n_1 = \dots = n_t = 1$, we have the empty graph, whose eigenvalues are all $0$. Otherwise, this graph does indeed have a smallest eigenvalue of $-1$, possibly with very large multiplicity.