I think that this should be fairly straightforward to prove: orient the edges of T1 from left to right, and of T2 from right to left.    Then every vertex has out-degree greater or equal to 1.  Hence if you start a path at a vertex, it can always be continued, unless it is forced to reach a vertex already seen, at which point you will have created a cycle (more correctly, a cycle with a path appended to it, but the cycle is there).

I think that this should be fairly straightforward to prove: orient the edges of T1 from left to right, and of T2 from right to left.    Then every vertex has out-degree greater or equal to 1.  Hence if you start a path at a vertex, it can always be continued, unless it is forced to reach a vertex already seen, at which point you will have created a cycle (more correctly, a cycle with a path appended to it, but the cycle is there).

What a good idea! Yes, this is straightforward and simple. I wonder why I could not think of this trick.

Is this trick widely known? I have read some books on Graph Theory (introductory textbooks). Most of them mention bipartite graph but pass by with only brief comments. For me, bipartite graph is very important, because it is the key tool to the general theory of Ricardian trade economy. 

Thanks a lot!.

I've not seen this used in quite this way before, but it is similar to two different methods: a) showing that graphs with minimum degree 2 have a cycle (hence trees must have vertices of degree 1) or directed graphs with minimum outdegree 1 have a directed cycle,  and 2) it is somewhat similar to the flavor of Schroder Bernstein's theorem that if you have a 1-1 map from A -> B, and a 1-1 map from B ->A, then you can construct a bijection.

I thank you again for your answers. They help me very much. The question I posed above is motivated by a study in the International Trade Theory of Ricardo type. 

The theorem I wanted to prove was rather classical. In 1961 Ronald Jones gave a definition of a class and claimed that each class has its unique optimum. My definition is a bit different from his, because I am more interested in the facets of production frontier (the set of maximal points). Jones was interested in the vertices of the world production frontier 

Jones, in his paper, did not give a formal proof but I want it for my study. It may provide me a deeper understanding of the trade theory. 

References:

Jones’s paper:

R. Jones 1961 Comparative Advantage and the Theory of Tariffs: A Multi-country, Multi-commodity Model, Review of Economic Studies 28(3): 161-175.

See also my recent paper:

Y. Shiozawa 2015 International Trade Theory and Exotic Algebras, Evolutionary and Institutional Economics Review 15(1): 177-212.      

 Yoshinori, 

So glad I've been able to help!  

Neil

Dear Neil,

I have reformulated my conjecture into a lemma:. 

Lemma

Let Km,n be a complete bipartite graph and T1 and T2 be two different spanning trees of Km,n. Introduce an orientation in T = T1 ∪ T2 as follows:

Then the directed graph T contains non-empty oriented cycle C. The cycle C contains edges that belong to  T1 but not to T2 and edges that belong to T2 but not to T1.

(Proof)

 The directed graph has two following properties:

• any left vertices have the same number for out- and in-degree.
• any right vertices have out degree equal of greater than 1. 

Start from an edge belonging to T1 and prolong this into a path  as far as this does not return to previous left  edges. This prolongation stops when we get a closed cycle.                                                                                                                   □   

The new expression is much more clear as meaning and indicates how to prove it.    

If you permit me, I would like to call this Neil Calkin lemma. 

This lemma is very useful one in Ricardian trade theory. This may also give some insight for tropical hyperplane arrangement.      

I will explain this briefly in the next post.

Yoshinori

Dear Yoshinori,

I'd rather you just called it a lemma, and, if you wish, acknowledge my assistance.

It's sufficiently close to what is known that I merely pointed you in the right direction:-)

I'll look forward to your next post:!

Neil

Dear Neil,

sorry to be late to come back . I am writing a paper and I used the above lemma in it. I expressed my gratitude and noted I owed this lemma to your suggestion. Unfortunately, as this paper is in Japanese, I cannot show you the paper. 

In the following posts, I will try to explain the core of Ricardo trade economy and its relation to bipartite graph, spanning trees, and even to tropical oriented matroid. 

 Ricardo trade economy

In an abstract form, Ricardo trade economy E is a couple of M ×N positive matrix A and M-vector q. An element aij of A is labor input coefficient to produce good j in country i and  qi of vector q is the labor power of country i.  The world production possibility set is given by

        P(E) =  {  y = (yj) |  yj = ∑isij ,  sij ≧0,  ∑j sij aij ≦ qi }.

Main task of trade theory is to know the price vector that is normal to a facet of P(E) and the pattern of competitive industries related to each facet.  

 An international value v = (w, p) which is a couple of two  linear forms over RM and  RN.  Here w is wage vector whose element wi is the wage rate of workers in country i and pi is the price of good j which is unique for all countries.  Let T be a spanning tree in the complete bipartite graph Km,n.  Then T defines an international value v(T) up to scalar multiplication. It is defined in such a way that It satisfies relations:

      wi aij = pj                                                                             (1)

whenever  (i,j) is an edge of T.  Later we write (i,j) ∈T.

An international value is said to be admissible when

     wi aij  ≧ pi .             ∀i, j                                                      (2)

Let T1 and T2 be two spanning trees and let T be the directed graph defined in the lemma. If there is a non-trivial cycle in T, then  two v(T1) and v(T2) cannot be admissible at the same time. 

 The lemma tells that there is only one spanning tree in the same class that defines an admissible vector. If v = v(T) is an admissible value associated to a spanning tree T, then there exists a facet in P(E) where p of v(T) is normal to the facet. The competitive pattern is in this case just spanning tree T.

In this way, many of trade theory is described in terms of bipartite graph and spanning trees.

The number of classes is the repeated combination of country labels sorted N-1 times. Thus the number take the form

                 (M + N - 2)! / (M - 1)! (N -1)! . 

 Form Scoins' formula the number of all spanning trees in Km,n is

                   MN-1 ・NM-1 .

So the spanning trees which have admissible values are very restricted. A natural question here is to ask how many spanning trees there are in a class. I will make this my next question in RG.

Counting spanning trees is well studied.  The matrix-tree theorem, due to Kirchoff, might well be useful to you.

https://en.wikipedia.org/wiki/Kirchhoff%27s_theorem

Dear Neil,

thank you for your suggestion. I do not worked well on Kirchhoff matrix-tree theorem. It seems a very powerful tool to count the number of  spanning trees in a fixed graph. My question is a bit different from enumeration of spanning trees in a graph. A class I defined is a set of graphs with some common properties. I could not find a way to use matrix -tree theorem method in my question.

I have posted my 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

If you have a good idea please post it in this above page.