# Number of spanning trees of $K_{3,3}$.

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?

-

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$.

-

I think using matrix tree theorem and the following theorem, the number of spanning tree can be enumerated. Let $\tau(G)$ be the number of spanning tree in a graph. If $e$ is not a loop then $\tau(G)=\tau(G-e)+\tau(G.e)$.

Here $G-e$ means removal of edge $e$ and $G.e$ means contaraction of edge $e$.

-