We identify a set of quantum graphs with unique and precisely defined spectral properties called regular quantum graphs. Although chaotic in their classical limit with positive topological entropy, regular quantum graphs are explicitly solvable. The proof is constructive: we present exact, convergent periodic orbit expansions for individual energy levels, thus obtaining an analytical solution for the spectrum of regular quantum graphs that is complete, explicit, and exact.