Given three non-isomorphic spanning trees of the complete graph K5, how many trees in each class?

3k Views Asked by At

The graph, K5 has 125 different spanning trees, which I beleive fit into three different non-isomorphic classes of spanning trees. However, I'm at odds as to how to figure out how many are in each class.

The trees I've found are, according to vertex degree:

(4, 1, 1, 1, 1) (3, 2, 1, 1, 1) (2, 1, 2, 1, 2)

How do I found out how many there are in each, to add up to 125?

1

There are 1 best solutions below

0
On BEST ANSWER

The first one you have listed is by far the easiest, we just pick the vertex we wish to be of degree 4 (out of the 5 choices) and everything else is determined. So there are 5 of the first type.

The next easiest class for me is the second, we can first choose the vertex we wish to be of degree 3 (of 5 choices) then of the remaining 4 vertices we pick the one we wish to be of degree 2. Finally we have to decide which of the last 3 vertices is connected to the degree 2 one (equivalently which two are connected to the degree 4 one) there are 3 choices and hence $5\cdot 4 \cdot 3 = 60$ isomorphic trees.

I'll leave the derivation of the last class up to you, it does require maybe a little more care to ensure you do not over count.