Counting of spanning trees of a complete graph - Porto, Anderson Luiz Pedrosa; Bessa, Vagner Rodrigues de; Aguiar, Mattheus Pereira da Silva; Vieira, Mariana Martins (Ciência e Natura, 2018)
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 E N and Kn the complete graph with n vertices. Then the number of spanning trees of Kn is established by n n-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.