The number of spanning trees in a complete graph of 4 vertices labelled A, B, C, and D is _________.

Question

Accepted Answer

16 Cayley's Formula tells us that the number of labelled spanning trees of a complete graph K_n is n^(n-2). For n=4, this gives 4^(4-2) = 4^2 = 16. Every spanning tree on 4 vertices has exactly 3 edges and is a tree (connected, acyclic).