2 problems

Dairyko et al.'s conjecture. Among connected graphs with fixed order $n$, the star graph $S_n$ minimizes the von Neumann entropy.

Quadratic-size sparsifier conjecture. Every directed graph with $k$ terminals admits a vertex cut sparsifier with $O(k^2)$ vertices.