# Proving Graph Theory Theorem: T and T' Spanning Trees of G

• tiagobt
In summary, the conversation discusses trying to prove a theorem using graph theory. The theorem states that if T and T' are two spanning trees of a connected graph G, and x is an edge that belongs to T but not T', and y is an edge that belongs to T' but not T, then (T-{x}) U {y} and (T'-{y}) U {x} are also spanning trees of G. The conversation includes an example to try and understand the theorem, and ultimately concludes that the theorem is correct. Suggestions for proving the theorem are also discussed.
tiagobt
I'm trying to prove the following theorem using graph theory:

T and T' are two spanning trees of the connected graph G. If x is an edge that belongs to T, but not to T' and y is an edge that belongs to T', but not T, then:

(T - {x}) U {y}
and
(T' - {y}) U {x}

are spanning trees of G.
I first tried to come up with an example:

Graph G
Vertices: a, b, c, d.
Edges: ab, ac, ad, bc, cd.

Spanning tree T
Vertices: a, b, c, d.
Edges: ab, ac, ad. (x = ac)

Spanning tree T'
Vertices: a, b, c, d.
Edges: ad, cd, bc. (y = bc)

Spanning tree (T - {x}) U {y}
Vertices: a, b, c, d.
Edges: [(ab, ac, ad) - (ac)] U bc = ab, ad, bc.
Which is really a spanning tree.

Spanning tree (T' - {y}) U {x}
Vertices: a, b, c, d.
Edges: [(ad, cd, bc) - bc] U ac = ad, cd, ac.
But this is a cycle that leaves b apart, not a spanning tree!

What did I do wrong?

Thanks,

Tiago

are you sure the question says prove: or is it prove/disprove?

If I recall correctly the theorem should be that given an x in the edge set of T but not in the edge set of T' then there exists a y in the edge set of T' that is not in the edge set of T such that ... (same conclusion)

so the y depends on x

Though I haven't looked this up... this is just my vague recollection

neurocomp2003 said:
are you sure the question says prove: or is it prove/disprove?
Yes, I'm sure. The question asks me to prove the theorem.

snoble said:
If I recall correctly the theorem should be that given an x in the edge set of T but not in the edge set of T' then there exists a y in the edge set of T' that is not in the edge set of T such that ... (same conclusion)

so the y depends on x

Though I haven't looked this up... this is just my vague recollection
I guess you're right: the theorem also says that, if there is an edge x in T, but not in T', then there is an edge y which is in T', but not in T. But I guess my first example follows this as well: x = ac is an edge that belongs to T, but not to T'; then there must be an edge y that belongs to T', but not to T. In my example, y = bc. Am I missing anything?

OK, I guess I figured it out. I misunderstood the theorem. I'll try to restate it:

T and T' are two spanning trees of a connected graph G. Suppose that x is an edge in T, but not in T'; then there is an edge y in T', but not in T, so that

(T - {x}) U {y}
and
(T - {y}) U {x}

are spanning trees of G.
What I understand is that, if there is x, then there must be at least one y that follows the theorem. In other words, not every edge that belongs to T' but not to T is the y that the theorem wants. In my example, bc is not good to be y. I could, however, choose x = ac and y = ad, finding the following spanning trees:

- ac, bc, dc

Is this right?

I believe that's the right idea. Of course proving it is a bit more of a challenge.

suggestion

I don't know if this will work, but could you do something like this:

Given spanning trees T and T', take an edge, x, in T that connects U to V that is not in T'.

Since x was the bridge from U to V, to re-create a tree, we have to replace it.

In T' there was also a U-V path, because in trees all vertices have to be connected, but we can also not duplicate any other path in the tree or create a circuit because the end result also has to be a tree...

So the problem lies in re-building that bridge.

What I am thinking is, can you say that you'll add the path without duplicating it because T and T' are not the same tree?

We did have that to begin with? Or not?

I'm not sure if maybe you could say use an algorithm to create a tree but avoid using that initial branch?

Another thing I'm thinking is maybe you could say that if you add the edge from the other tree, you will create a circuit so there are 2 paths from U to V, then break the circuit by taking out the original x from T and you will still have a tree.

I don't know if either of these approaches will work for you, tell me what you think.

- Vanes.

ah for the restated question it is a simple PROOF (10-15min)

the question is about disconnected graphs and parity.
[1]T -{x} = ?
[2]T'+{x} = ?
Apply parity of [1] on what you can think of for [2]

EASY AS PIE

## 1. What is a spanning tree in graph theory?

A spanning tree in graph theory is a subgraph of a graph that includes all of the vertices and is also a tree, meaning it has no cycles. It is a connected and acyclic subgraph that is used to analyze the structure of a larger graph.

## 2. What is the significance of T and T' in the theorem?

T and T' are two distinct spanning trees of a graph G. The theorem states that if T and T' are both spanning trees of G, then they have a common edge. This common edge is known as the bridge edge, and it connects two components of the graph.

## 3. How can we prove the theorem?

The theorem can be proven using induction. The base case is when the graph G has only one edge, which is trivially true. Then, we assume that the theorem holds for all graphs with fewer than k edges. Finally, we show that if the theorem holds for all graphs with k edges, then it also holds for a graph with k+1 edges.

## 4. What is the practical application of this theorem?

This theorem has practical applications in network design and optimization. It helps in identifying critical edges in a network that, if removed, can disconnect the network. It also aids in finding the minimum number of edges needed to connect all vertices in a network.

## 5. Are there any other similar theorems in graph theory?

Yes, there are several other theorems in graph theory that deal with spanning trees. Some of them include the Cut Property, the Existence of Spanning Trees in a Connected Graph, and the Characterization of Spanning Trees in Bipartite Graphs.

Replies
1
Views
771
Replies
7
Views
1K
Replies
21
Views
1K
Replies
1
Views
1K
Replies
13
Views
1K
Replies
5
Views
1K
Replies
1
Views
1K
Replies
1
Views
1K
Replies
7
Views
2K
Replies
1
Views
2K