Graph Problem: Reconstructing Spanning Trees

[user1616]

Graph problem!

Proove that:

If we have a matrix
|e11 e12 ... e1n|
|e21 e22 ... e2n|
| ..... |
|en1 en2 ... enn|

(eij edges of a graph G)
where every row is a spanning tree of G

then
there is a recomposition of every row so that the columns are also spanning trees of G.

 

[Pere Callahan]

It might be good to start with the definition of a spanning tree...

 

[user1616]

well
A spanning tree is a cohesive connected graph (T) with no loops that contains all the vertices of G...
...any idea?

 

[dodo]

Refresh my memory. Is there somewhere a theorem stating that, in a graph of n+1 vertices, any set of n (distinct) edges is a spanning tree?

Edit: Oh, sorry, I should've said "any tree of n distinct edges is spanning". If the set contains a loop, it will not comprise n+1 distinct vertices.

 

[user1616]

Yes there should be no loops.
Anyway
I read a theorem that may help. It says:

We have 2 trees T,T'.
For every edge (x) that belongs to T there is an edge (Y) that belongs to T' so that:
(T-{x})U{y} and (T'-{y})U{x} are also trees.

I'm trying to use it...

 

[user1616]

Well using it I just prooved it for the first column.
For the next columns, in the previews theorem I should know that for every x' != x
there is a y' != y. (!= is different)

Can anybody tell me whether this is true or not?
Also if it is, does anybody have any proof?

 

[user1616]

Thanx anyway.
I prooved it.