Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 1 down vote accepted

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

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.