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

[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

 

[neurocomp2003]

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

 

[snoble]

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

 

[tiagobt]

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

Yes, I'm sure. The question asks me to prove the theorem.

 

[tiagobt]

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?

 

[tiagobt]

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:

- ab, ad, bc
- ac, bc, dc

Is this right?

 

[snoble]

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

 

[Vanes63]

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.

 

[neurocomp2003]

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