The number of spanning trees in a complete graph of 4 vertices labelled A, B, C, and D is _________
Answer
16
Explanation
By Cayley’s formula, the complete graph on \(n\) labelled vertices has \(n^{n-2}\) spanning trees, so \(K_{4}\) has \(4^{4-2} = 16\).
A direct count agrees. A spanning tree on 4 vertices has 3 edges, and \(K_{4}\) has 6 edges, so there are \(\binom{6}{3} = 20\) sets of 3 edges. Three edges on four vertices fail to form a tree only when they make a triangle (leaving the fourth vertex isolated), and \(K_{4}\) has 4 triangles: \(20 - 4 = 16\). They are the 12 paths and the 4 stars on A, B, C, D.
Answer: 16