I want to know how many different spanning trees of $K_{3,3}$ are there.
I know, that there's a nice formula that says, that it's $3^2*3^2$, but the proof of it is way beyond my scope, so I'll need to be clever in finding the number another way.
Well, we have a complete bipatriate graph here. Since it's supposed to be a spanning tree then we have to use $5$ edges, so the sum of degrees is $10$. Now since this is a bipatriate graph, the number of vertices leaving component $A$ has to be the same as the number of edges leaving component $B$, so over each side we have the number of edges equal to $5$. So I think we just have to about how many different pairs of $(a_1,a_2,a_3|b_1,b_2,b_3)$ are there, where each $a_x,b_x$ (which designate the degrees of each vertices of components) is in $\{1,2,3\}$ and $a_1+a_2+a_3=5$, right?
$(3,1,1|2,2,1)$ – $2$ trees fullfill this (we can choose which vertices connect to each of vertices of degree 2 in $B$, so we have $9*2$ total, because there are 9 different position of $3$ in the first part, and $1$ in the second). We can reverse the pair for another $18$ trees.
$(3,1,1|3,1,1)$ – $1$ tree fullfills this, so we have $9$ total trees.
$(2,2,1|2,2,1)$ – $4$ trees fulfills this (we choose one which is shared between vertices of degree $2$ in $A$, and divide the rest between them two different ways), for grand $9*4=36$ total.
So I have $81$ different trees. But is it a coincidence I am right or is my way of solving the problem correct?
Best Answer
As you said, there will be five edges, and each $A$-point will be incident to least one edge. There are $2$ partitions of $5$ into $3$ nonempty parts, namely $(3,1,1)$ and $(2,2,1)$.
As for $(3,1,1)$, you can choose the $A$-vertex of degree $3$ in three ways, and you can connect each of the other two $A$-vertices to a $B$-vertex at libitum in $9$ ways. Each of these $27$ times you will get a spanning tree of $K_{3,3}$.
Concerning $(2,2,1)$ you can choose the $A$-vertex of degree $1$ in $3$ ways and connect it with the $B$-vertex of your choice in $3$ ways. Then you can connect the first $A$-vertex of degree $2$ with two $B$-vertices of your choice in $3$ ways and connect the second $A$-vertex of degree $2$ with two $B$-vertices of your choice, but not the same two as before, in $2$ ways, giving a total of $54$ possibilities, and each of these leads to a spanning tree of $K_{3,3}$.
Therefore the overall total is $81$.