Proof involving edges in different trees

Question

In the proof of the Kruskal's algorithm given in class, we made this statement:

given two different trees $T$ and $T'$ on $n$ vertices, and given and edge $e \in E(T)\setminus E(T')$, consider the edge $e'$ such that $e' \in E(T')\setminus E(T)$ and $T\setminus \{e\} \cup \{e'\}$ is a tree on $n$ vertices ($E(T),E(T')$ denote the edge sets of $T$ and $T'$ respectively).

Now, intuitively I believe that such an $e'$ exists, but can I say that this always true?

Thank you

Answer 1

Deleting edge $e$ from $T$ gives two connected components (call their vertex sets $A$ and $B$). Since $T'$ is connected, it must contain some edge $e'$ from $A$ to $B$. Add that edge $e'$ to $T-e$, and it will be connected again; since this returns us to the minimum number of edges, the result is another spanning tree.

Answer 2

I am assuming you are talking about spanning trees. In Matroid theory (and specifically cycle matroids in your case) What you are referring to is called the "base exchange property".