• Support PF! Buy your school textbooks, materials and every day products Here!

Graph problem

  • Thread starter user1616
  • Start date
5
0
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.
 

Answers and Replies

It might be good to start with the definition of a spanning tree...
 
5
0
well
A spanning tree is a cohesive connected graph (T) with no loops that contains all the vertices of G...
...any idea?
 
695
2
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:
5
0
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...
 
5
0
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?
 
5
0
Thanx anyway.
I prooved it.
 

Related Threads for: Graph problem

  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
6
Views
1K
  • Last Post
Replies
16
Views
2K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
1
Views
609
  • Last Post
Replies
5
Views
2K
Top