# 2021-18 Independent sets in a tree

Let $$T$$ be a tree (an acyclic connected graph) on the vertex set $$[n]=\{1,\dots, n\}$$.
Let $$A$$ be the adjacency matrix of $$T$$, i.e., the $$n\times n$$ matrix with $$A_{ij} = 1$$ if $$i$$ and $$j$$ are adjacent in $$T$$ and $$A_{ij}=0$$ otherwise. Prove that the number of nonnegative eigenvalues of $$A$$ equals to the size of the largest independent set of $$T$$. Here, an independent set is a set of vertices where no two vertices in the set are adjacent.

GD Star Rating