The number of spanning trees in a complete graph of 4 vertices labelled A, B,…

Answer: 16

Key idea: use Cayley’s formula for the number of spanning trees in a complete graph.

• Cayley’s formula: a complete graph on n labelled vertices has n^{n-2} spanning trees.

• Here n = 4, so the number is 4^{4-2} = 4^2 = 16.

Optional remark: this result can be proved using Prüfer codes, which give a bijection between labelled trees on n vertices and sequences of length n-2 with entries from the n labels.