학과 세미나 및 콜로퀴엄

SAARC 세미나

IBS-KAIST 세미나

대학원생 세미나

학술회의 및 워크샵

학생 뉴스

북마크

게시판

동문 뉴스

Problem of the week

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.