existence of a spanning tree

Question

Let $T$ and $T'$ be two spanning trees of a connected graph $G$. Suppose that an edge $e$ is in $T$ but not in $T'$. Show that there is an edge $e'$ in $T'$, but not in $T$, such that $T-\{e\}\cup\{e'\}$ and $T'-\{e'\}\cup\{e\}$ are spanning trees of $G$.

Answer 1

Fact 1: Let G be connected. If order of G = size of G +1 then G is acyclic. Thus G is a tree

Fact 2: Let G be an acyclic graph with order n and size n-1, then G is connected. Thus G is a tree

Proof of the statement of the question (Throughout my proof n is order of G):

I will call the edge that was described in the question e (Let e={u,v}). Since T' is connected and u,v are vertices in T', therefore there exists a path in T'from u to v. Let this path be $w^0w^1...w^r$ for some vertices $w^0,w^1...,w^r$ in G (where $w^0=u$ and $w^r=v$ ).

Claim 1: There exists $0<=i<=r-1$ such that the path from $w^i$ to $w^{i+1}$ in T contains the edge e. Proof: Suppose that for all $0<=i<=r-1$ the path from T from $w^i$ to $w^{i+1}$ (call the path $P^i$) does not contain the edge e. Now we consider the walk made by going from $P^1$ to $P^2$ .... till $P^{r-1}$. This is a walk in T that starts at u and ends at v. Moreover, this walk does not include the edge e. Using fact 1 we deduce that there exists a path (Q) from u to v such that Q does not contain the edge e. Now Q with the edge e form a cycle. This contradicts the fact that T is acyclic.

Call the edge {$w^i,w^{i+1}$} e'.(where i satisfies claim 1)

Claim 2: T−{e}∪{e′} is acyclic.

Proof: Suppose there exists a cycle in T−{e}∪{e′}. Since T is acyclic, therefore T-{e} is acyclic. Thus we know that the cycle must contain the edge e' ({$w^i,w^{i+1}$}). Now consider the part cycle without e', this is a path in T-{e} from $w^i$ to $w^{i+1}$. This contradicts the way {$w^i,w^{i+1}$} was chosen.

Claim 3: T−{e'}∪{e} is connected

Proof: To make the proof here short, I will just mention the idea of the proof. There is a walk from $w^i$ to $w^{i+1}$ in T−{e'}∪{e}. This walk is $w^i,w^{i-1},...,w^0,w^{r-1},w^{r-2},...,w^{i+1}$. Now the effect of removing e' on connectivity is gone by adding the edge e.

Claim 4: T−{e'}∪{e} and T−{e}∪{e′} have n vertcies and n-1 edges. Proof: This is easy to verify.

Using Fact 1 we deduce that T−{e'}∪{e} is a tree

Using Fact 2 we deduce that T−{e}∪{e'} is a tree Since both trees have n vertices, thus they are spanning trees.

Answer 2

Add $e$ to $T'$, get a unique cycle by Fact 1 below. Now $T\setminus e$ has 2 components. As we go along the cycle from one vertex of e to another we have to switch the components of $T$ at some point. Hence there is an edge $e'$ in that cycle with vertices in different components of $T\setminus e$ (it is automatically not in $T$). We claim that these $e, e'$ are as wanted.

Indeed $e \cup T' \setminus e'$ is obtained from $e \cup T'$ by removing an edge from the unique cycle, so by Fact 2 below it is a spanning tree. On the other hand $e' \cup T \setminus e$ is connected, hence by Fact 3 it is a spanning tree.

We used the three facts:

Fact 1: Adding an edge to a spanning tree produces a spanning subgraph with exactly one cycle.

Fact 2: Removing an edge form the cycle of spanning subgraph with exactly one cycle produces a spanning tree.

Fact 3: A connected graph with n vertices and n-1 edges is a tree.

All of these follow trivially from the fact that dimension of space of cycles is obtained from formula $V-E$= number of components - dimension of the space of cycles, which is manifestation of $C_0-C_1=H_0-H_1$ for the 1-d cell complex. They can also be proved independently.