Spanning Trees Discrete Math

Question

Given G = ( { a, b, c, d, e, f }, E ) and |E| = 15, how many spanning trees can be formed from G if G is undirected?

Answer: _ _ _ _ _

Answer 1

The core insight needed here is that with 6 vertices, there are ₆C₂=15 edges in the complete graph, so G is K₆. Cayley's formula tells us there are n^n-2 spanning trees of K_n, so in particular here we have 6⁴=1296.

There are many nice proofs of Cayley's formula; I find the most accessible to be through Prufer sequences, which make a simple algorithmic bijection between certain types of lists of the nodes and unique spanning trees. I don't know if that's the angle your class is looking for or not - feel free to add clarifying information if you think there's a specific different sort of concept/theorem you expect you're being asked to apply here! - but if you're interested and haven't seen them, wikipedia has a nice description of the process: https://en.wikipedia.org/wiki/Pr%C3%BCfer_sequence (funky characters in the middle there because there's an umlaut over the u in Prufer's name)