Counting of spanning trees of a complete graph




Trees, Spanning Trees, Cayley’s Formula, Complete Graphs, Inverse Process of Cayley-Prufer


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.


Download data is not yet available.

Author Biographies

Anderson Luiz Pedrosa Porto, Universidade Federal dos Vales do Jequitinhonha e Mucuri, Diamantina, MG

Professor na Universidade Federal dos Vales do Jequitinhonha e Mucuri, Diamantina, MG

Vagner Rodrigues de Bessa, Universidade Federal de Viçosa, Rio Paranaiba, MG

Professor Adjunto IV na Universidade Federal de Viçosa - Campus Rio Paranaíba.

Mattheus Pereira da Silva Aguiar, Universidade Federal de Minas Gerais, Belo Horizonte, MG

Mestrado em Matemática pela Universidade Federal de Minas Gerais


Abu-Sbeih, M. Z. (1990). On the number of spanning trees of Kn and Km;n. Discrete Mathematics, North-Holland, 84, 205–207.

Bondy, J. A., Murty, U. R. S. (1982). Graph theory with applications, 5o edn. New York: North Holland.

Domingues, H. H., Iezzi, G. (2003). Algebra Moderna ´ , 4o edn. Sao Paulo: Atual.

Fracasso, P. (2008). Analise de t ´ ecnicas para amostragem e sele ´ c¸ao de v ˜ ertices no planejamento probabil ´ ´ıstico de mapa de rotas. Dissertac¸ao de mestrado, Escola polit ˜ ecnica da USP. ´

Harary, F. (1969). Graph Theory, 1o edn. Menlo Park: Addison Wesley Pub. Co. Inc..

Junior, E. R. H., Nicoletti, M. C. (2006). ´ Fundamentos da teoria dos grafos para computac¸ao ˜ , 1o edn. Sao Carlos: Edufscar. ˜

Konzen, D. C. (1997). Automata and computability, 1o edn. Springer New York.

Orsini, L. Q., Consonni, D. (2002). Curso de circuitos eletricos ´ , 2o edn. Edgard Blucher Ltda. ¨

Wilson, R. J. (1996). Introduction to graph theory, 4o edn. London: Prentice-Hall.

Wu, B. Y., Chao, K. (2004). Spanning trees and optimization problems, 1o edn. Chapman & Hall/CRC Press, USA.



How to Cite

Porto, A. L. P., Bessa, V. R. de, Aguiar, M. P. da S., & Vieira, M. M. (2018). Counting of spanning trees of a complete graph. Ciência E Natura, 40, e19.




Most read articles by the same author(s)