On Brouwer's Laplacian conjecture

Abstract

Brouwer's Laplacian conjecture states that the sum of the largest $k$ eigenvalues of a graph's Laplacian is less than or equal to the number of edges plus $\left(\genfrac{}{}{0ex}{}{k+1}{2}\right)$. We give a proof of this conjecture. Our proof relies on the Grone--Merris--Bai theorem for \emph{split} graphs. We also show the converse, thereby establishing an equivalence between Brouwer's conjecture and the Grone--Merris--Bai theorem.