- #1

tiagobt

- 31

- 0

I first tried to come up with an example: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.

**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