We consider the Schroedinger operator on graphs and study the spectral statistics of a unitary operator which represents the quantum evolution, or a quantum map on the graph. This operator is the quantum analogue of the classical evolution operator of the corresponding classical dynamics on the same graph. We derive a trace formula, which expresses the spectral density of the quantum operator in terms of periodic orbits on the graph, and show that one can reduce the computation of the two-point spectral correlation function to a well defined combinatorial problem. We illustrate this approach by considering an ensemble of simple graphs. We prove by a direct computation that the two-point correlation function coincides with the CUE expression for 2x2 matrices. We derive the same result using the periodic orbit approach in its combinatorial guise. This involves the use of advanced combinatorial techniques which we explain.