# Graph problem

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.

Related Precalculus Mathematics Homework Help News on Phys.org
It might be good to start with the definition of a spanning tree...

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

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.

Last edited:
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...

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?

Thanx anyway.
I prooved it.