A note on the von Neumann entropy of random graphs

In this note, we consider the von Neumann entropy of a density matrix obtained by normalizing the combinatorial Laplacian of a graph by its degree sum. We prove that the von Neumann entropy of the typical Erdös–Rényi random graph saturates its upper bound. Since connected regular graphs saturate this bound as well, our result highlights a connection between randomness and regularity. A general interpretation of the von Neumann entropy of a graph is an open problem.