Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$.

share|cite|improve this question
Welcome to math.SE, Rik! Since you are new, I wanted to let you know a few things about the site. In order to get the best possible answers, it is helpful if you say in what context you encountered the problem, and what your thoughts on it are; this will prevent people from telling you things you already know, and help them give their answers at the right level. Also, many find the use of imperative ("Prove", "Solve", "Show" etc.) to be rude when asking for help; please consider editing your post. – amWhy Nov 10 '12 at 17:41

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.

share|cite|improve this answer
More importantly, I hope someone gives a shorter proof. – Amr Nov 10 '12 at 23:11
I think I found one. – Max Nov 11 '12 at 3:57

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.