In 1889, Arthur Cayley published an article that contained a formula for counting the spanning trees of a complete graph. This theorem says that: Let n ∈ N and Kn the complete graph with n vertices. Then the number of spanning trees of Kn is established by nn−2. The present work is constituted by a brief literary review about the basic concepts and results of the graph theory and detailed demonstration of the Cayley’s Formula, given by the meticulous construction of a bijection between the set of the spanning trees and a special set of numeric sequences. At the end we bring an algorithm that describes a precise construction of the spanning trees obtained of Kn from Cayley-Prufer sequences.
