  We introduce a Markov Chain Monte Carlo algorithm which samples from the
space of spanning trees of complete graphs using local rewiring operations
only. The probability distribution of graphs of this kind is shown to depend on
the symmetries of these graphs, which are reflected in the equilibrium
distribution of the Markov chain. We prove that the algorithm is ergodic and
proceed to estimate the probability distribution for small graph ensembles with
exactly known probabilities. The autocorrelation time of the graph diameter
demonstrates that the algorithm generates independent configurations
efficiently as the system size increases. Finally, the mean graph diameter is
estimated for spanning trees of sizes ranging over three orders of magnitude.
The mean graph diameter results agree with theoretical asymptotic values.
