The spectral theory of quantum graphs is related via an exact trace formula with the spectrum of the lengths of periodic orbits (cycles) on the graphs. The latter is a degenerate spectrum, and understanding its structure (i.e.,finding out how many different lengths exist for periodic orbits with a given period and the average number of periodic orbits with the same length) is necessary for the systematic study of spectral fluctuations using the trace formula. This is a combinatorial problem which we solve exactly for complete (fully connected) graphs with arbitrary number of vertices.