Bijection and spanning trees 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?
 A: 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

Lemma 1. Let $$ S_{a_1}\cup\ldots\cup S_{a_k}=\{b_1,\ldots,b_s\}. $$
Then a graph $H=T_1+a_1+\ldots+a_k-b_1-\ldots-b_s$ has no cycles.

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.

Lemma 2. 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$ the following inequality
holds $$ |S_{a_1}\cup\ldots\cup S_{a_k}|\geq k $$

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

Theorem. Let $G$ be a connected graph, and let $T_1$ and $T_2$ be two
of its spanning trees. Then 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.

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.
