I present a proposal, originally motivated by a result in graph theory: the entropy function of a density matrix naturally associated to a simple undirected graph, is maximized, among all graphs with a fixed number of links and nodes, by regular graphs.I recover this result starting from the Hamiltonian operator of a non-relativistic quantum particle interacting with the loop-quantized gravitational field and setting elementary area and volume eigenvalues to a fixed value. This operator provides a spectral characterization of the physical geometry, and can be interpreted as a state describing the spectral information about the geometry available when geometry is measured by its physical interactionwith matter. It is then tempting to interpret the associated entropy function as a genuine physical entropy: I discuss the difficulties of this interpretation and I present a possible viable definition of quantum-gravitational entropy.