Use Kirchhoff's matrix tree theorem.  Let  M  =  D  -  A, where D is the diagonal degree matrix and A is the adjacency matrix.  Take any cofactor, and reduce to upper triangular form.  The product down the diagonal gives the formula wanted.

Additional comment.  there is an extension (due to Austin) to spanning trees of complete multipartite graphs, say k-partite with sets of sizes a1, a2, . . . ak and order n.

Number of trees = n^(k-2) x product of (n-ai)^(ai-1)

For k = 2, this is the same as Scoins formula.

Thank you, Allen, for your quick answer.  However, how about using Kirchhoff's matrix tree theorem? Can we say it is elementary? At least for those people who barely know graph theory, it is not.

I am thinking of my colleagues, who are economists and seldom know much about graph theory.  Is there no way to prove Scoin's formula without  a help of Kirchhoff's theorem or any other highly advanced graph theory? 

I received a personal communication from Allen J. Schwenk that the proof that uses Kirchhoff Matrix is the simplest proof that he knows. It  is important information. I hope that some specialists in graph theory will challenge to find a new elementary proof.

It will be a challenging problem for young new specialists in graph theory.

 If you are willing to assume Prüfer's bijection (trees Prüfer sequences), then a proof is not too difficult (see English wikipedia on Prüfer sequences).

Dear Professor Yoshinori Shiozawa,

I suggest you to take a look at the following book:

C. Berge, Principles of Combinatorics, Academic Press, 1971. 

On page 108, Corollary 4.

Regards,

Wiwat Wanicharpichat

Thank you,  Christiaan E. van de Woestijne.

Although I have not yet clarified all the points, the proof that uses Prüfer's sequences is rather elementary. At least, I may give a story how the Scoin's formula is obtained.

I have found that a tree in a bipartite tree in Km,n has a Prüfer's sequence with n-1 nodes of the left part and  m-1 nodes in the right part, but some nodes in the right part come in between the nodes of left part. I am wondering why the order of nodes in the sequence does not matter to the identification of trees.  

Can you explain this point? 

Now that the Prufer code has been mentioned, I can see how to do it.  Put all the low labels on the left side and high labels on the right side.  Form the high seq of len m-1 in n^(m-1) ways and the low seq in m^(n-1) ways.  Notice that every edge joins a low label to a high one.

Now we could merge these into a single seq in binom(n+m-2,n-1) ways, but only one of them will yield the desired partition into m by n.  How can we identify the unique proper merger?  It is critical that this can be done in only one way.

The inverse procedure leading from a code to a tree places an edge between the first entry in the merged list and the lowest label omitted from the combined list.  If this lowest omitted label is "high", choose the first low entry to be first on the merged list.  If this omitted entry is itself "low", place the first high entry first on the merged list.  Continuing to use the inverse procedure in this way causes us to form a unique merged list and also a unique tree with set partition m by n.

Thus each of the n^(m-1) high seqs merges uniquely with each of the m^(n-1) low seqs to form a unique tree that is a spanning tree of the K sub n,m.

Thank you, Allen.

It seems that I have to work two or three days before I will understand all.

I realize my last answer was just a sketchy outline.  To gain good understanding, first practice using Prufer technique to convert any tree (not necessarily from K(n,m) ) to a sequence.  Use the inverse procedure to reconstruct the tree.  Do several examples until you are comfortable with both procedures.  Then reread my answer and do some examples.

You may surprised to know that I was attending to the SIAM AG15 conference, which was held last week at Daejeon, Korea. I talked in a small session on applications of Algebraic Geometry on economics. The title of my talk was Subtropical convex Geometry as Ricardian theory of International Values. I attended some other sessions and some were inspirational, although majority of the lectures were out of my reach.

 I have examined some simple cases after your advice.

 K2,3 case: there are only 12 spanning trees. I checked all of them. Here is the result:

 A123 B1             1AA

A123 B2             2AA

A123 B3             3AA

A12 B13             A1B

A12 B23             A2B

A13 B12             B1A

A13 B23             A3B

A23 B12             B2A

A23 B13             B3A

A1 B123             1BB

A2 B123             2BB

A3 B123             3BB 

Note: A, B indicate countries, whereas 1, 2, 3 indicates commodities. It is understand that A < B, and A, B precedes 1, 2, 3. 

The first column shows the spanning trees. For example, A123 B1 means that it is a graph with the set of edges {A1, A2, A3, B1} and so on. 

The second column shows Prüfer sequence. 

I see that capital letters appears 2 time and numbers 1 time for every sequence. If we ignore the order between capital letters and numbers, the set of sequences covers all combinations of A, B and 1, 2, 3 separately.

Next table is the result for K3,3 (81 spanning trees) 

A123 B1 C1                       11AA

A123 B1 C2                       12AA

A123 B1 C3                       13AA

A123 B2 C1                       23AA

A123 B2 C2                       22AA

A123 B2 C3                       23AA

A123 B3 C1                       31AA

A123 B3 C2                       32AA

A123 B3 C3                       33AA

A12 B13 C1                       1A1B

A12 B13 C2                       2A1B

A12 B13 C3                       3A1B

A12 B23 C1                       1A2B

A12 B23 C2                       2A2B

A12 B23 C3                       3A2B

A13 B12 C1                       1B1A

A13 B12 C2                       2B1A

A13 B12 C3                       3B1A

A13 B23 C1                       1A3B

A13 B23 C2                       2A3B

A13 B23 C3                       3A3B

A23 B12 C1                       1B2A

A23 B12 C2                       2B2A

A23 B12 C3                       3B2A

A23 B13 C1                       1B3A

A23 B13 C2                       2B3A

A23 B13 C3                       3B3A

A12 B1 C13                       1A1C

A12 B1 C23                       1A2C

A12 B2 C13                       2A1C

A12 B2 C23                       2A2C

A13 B1 C12                       C1A1

A13 B1 C23                       1A3B

A13 B1 C12                       1C2A

A13 B1 C23                       1A3C

A13 B2 C12                       2C1A

A12 B2 C23                       2A2C

A12 B3 C13                       3A1C

A12 B3 C23                       3A2C

A12 B1 C13                       1A1C

A12 B1 C23                       1A2C

A12 B2 C13                       2A1C

A12 B2 C23                       2A2C

A12 B3 C13                       3A1C

A12 B3 C23                       3A2C

A1 B123 C1                       11BB

A1 B123 C2                       12BB

A1 B123 C3                       13BB

A1 B12 C13                       1B1C

A1 B12 C23                       1B1C

A1 B13 C12                       1C1B

A1 B13 C23                       1B3C

A1 B23 C12                       1C2B

A1 B23 C13                       1C3B

A1 B1 C123                       11CC

A1 B2 C123                       12CC

A1 B3 C123                       13CC

A2 B123 C1                       21BB

A2 B123 C2                       22BB

A2 B123 C3                       23BB

A2 B12 C13                       2B1C

A2 B12 C23                       2B2C

A2 B13 C12                       2C1B

A2 B13 C23                       2B3C

A2 B23 C12                       2C2B

A2 B23 C13                       2C3B

A2 B1 C123                       21CC

A2 B2 C123                       22CC

A2 B3 C123                       23CC

A3 B123 C1                       31BB

A3 B123 C2                       32BB

A3 B123 C3                       33BB

A3 B12 C13                       3B1C

A3 B12 C23                       3B2C

A3 B13 C12                       3C1B

A3 B13 C23                       3B3C

A3 B23 C12                       3C2B

A3 B23 C13                       3C3B

A3 B1 C123                       31CC

A3 B2 C123                       32CC

A3 B3 C123                       33CC 

I see that capital letters appears 2 time and numbers 2 time for every sequence. If we ignore the order between capital letters and numbers, the set of sequences covers all combinations of A, B, C and 1, 2, 3 separately. 

However, puzzles remain. Why do letters (vertices at the left) and numbers (vertices at the right) arrange in this particular way? Why can we ignore the positions of numbers among letters? Is there any rule for the alternations of letters and numbers? 

Can you explain?

I have posted a new question which is closely related to this question:  

Do you know the number of all spanning trees of a given class?

https://www.researchgate.net/post/Do_you_know_the_number_of_all_spanning_trees_of_a_given_class

All these mathematical problems compose a part of the theory of Ricardo trade economy.

Ricardo trade economy is an economy where there are many countries which engage in trade of consumer goods but do not export or import input goods. Of course, this is a very special trade economy but it has a good and interesting mathematical structure. For a  rapid introduction, see my recent paper

International trade theory and exotic algebra

https://www.researchgate.net/publication/280646264_International_trade_theory_and_exotic_algebra

Of course, the Ricardo trade economy in the above sense is too strict. The economy which permits input trade (or trade in intermediate goods) is called Rirado-Sraffa trade economy. A trade theory is build for this RS trade economy, but it requires a special treatment, because simple generalization of Ricardo trade economy framework does not work for RS trade economy.   

Article International trade theory and exotic algebra