Given two spanning trees $T_1$ and $T_2$, prove that there exists a bijection $h$ from $T_2 \setminus T_1$ to $T_1 \setminus T_2$ such that for every $a \in T_2 \setminus T_1$, $T_1 - h(a) + a$ is a spanning tree.
So far I have proved that if $u \in T_1\setminus T_2$, there exists $v$ in $T_2 \setminus T_1$ such that $T_2 - v + u$ and $T_1 - u + v$ are spanning trees at the same time. What else could I do?
It's a little long-winded reasoning. But the problem is quite interesting.
Let $a\in T_2\setminus T_1$. The graph $T_1+a$ contains exactly one cycle. Among the edges of this cycle at least one edge is not contained in $T_2$. Denote this edge by $b$. We have $b\in T_1\setminus T_2$ and $T+a-b$ is a tree.
Thus for any edge $a\in T_2\setminus T_1$ there exists at least one edge $b\in T_1\setminus T_2$ such that $T_1+a-b$ is a tree.
Let us denote by $$ S_a=\{b\in T_2\setminus T_1\mid T_1+a-b \hbox{ is a tree}\}. $$ We see that $S_a\neq\varnothing$ for any $a\in T_2\setminus T_1$.
Our goal is to take advantage of Philip Hall's theorem on a system of distinct representatives (see, for example, M. Hall's book 'Combinatorial Theory', Theorem 5.1.1).
To do this we have to check that $$ |S_{a_1}\cup\ldots\cup S_{a_k}|\geq k $$ for any integer $k$ $(1\leq k\leq |T_2\setminus T_1|)$ and any $a_1,\ldots,a_k\in T_2\setminus T_1$.
First we prove
Proof. If the graph $H$ has a cycle $C$, then the cycle $C$ includes one or more edges from the set $\{a_1,\ldots,a_k\}$, i.e. $p=|C\cap\{a_1,\ldots,a_k\}|\geq1$.
The case $p=1$ is impossible by the definition of $S_a$. Let $p>1$ and $a_1,\ldots,a_p\in C$. We can assume that these edges enter $C$ in the specified order if we bypass $C$ in one of two possible directions. Let in addition $a_i=u_iv_i$ ($u_i,v_i$ vertices of our graph) and the direction from $u_i$ to $v_i$ coincides with the direction of the cycle $C$.
Since $T_2$ is a tree, not all edges of the cycle $C$ lie in $T_2$. Let $b\in C$ and $b\in T_1\setminus T_2$. Let us assume that $b$ lies between $a_1$ and $a_2$ on the cycle $C$ and $b=u_0v_0$ and the direction from $u_0$ to $v_0$ coincides with the direction of the cycle $C$ (see figure).
Let $U$ be the set of all vertices lying on $C$ between $v_0$ and $u_2$ ($v_0,u_2\in U$, $u_0\notin U$). Let $V$ be the set of all vertices lying on $C$ between $v_p$ and $u_1$ ($v_p,u_1\in V$, $v_1\notin V$). Clearly, $U\neq\varnothing$ and $V\neq\varnothing$. Since $T_1$ is connected, there exists a path $P$ between $U$ and $V$ in $T_1$. We can assume that all vertices of the path $P$ except the beginning and the end do not lie on the cycle $C$.
Consider a cycle $C'$ consisting of $P$ and that arc of the cycle $C$ on which the edges $b$ and $a_1$ lie. All edges of the cycle $C'$ except edge $a_1$ belong to $T_1$, and $b\in T_1\setminus T2$. This means that $b\in S_{a_1}$. By the definition of graph $H$ this is impossible.
Consequently, we proved that graph $H$ has no cycles. Lemma 1 is proved.
Proof. Let on the contrary, for some $a_1,\ldots,a_k\in T_2\setminus T_1$ holds $$ |S_{a_1}\cup\ldots\cup S_{a_k}|<k $$ and $$ S_{a_1}\cup\ldots\cup S_{a_k}=\{b_1,\ldots,b_s\},\ s<k. $$ The graph $H=T_1+a_1+\ldots+a_k-b_1-\ldots-b_s$ has $|E(H)|=|E(T_1)|+k-s$ edges. So $|E(H)|>|E(T_1)|$. It follows that $H$ has cycles. On the other hand, by Lemma 1 the graph $H$ has no cycles. Contradiction. Lemma 2 is proved.
Now we prove
Proof. Let $T_2\setminus T_1=\{a_1,\ldots,a_m\}$ and $S_i=S_{a_i}$ for all $i=1,\ldots,m$. In view of Lemma 2, all the conditions of Philip Hall's theorem on a system of distinct representatives are satisfied. Therefore there exist distinct representatives $b_i\in S_i$, $i=1,\ldots,m$, $b_i\neq b_j$, when $i\neq j$.
The bijection $h$ is now constructed by the rule $h(a_i)=b_i$. Theorem is proved.