1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Graph problem

  1. Apr 28, 2008 #1
    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

    there is a recomposition of every row so that the columns are also spanning trees of G.
  2. jcsd
  3. Apr 28, 2008 #2
    It might be good to start with the definition of a spanning tree...
  4. Apr 30, 2008 #3
    A spanning tree is a cohesive connected graph (T) with no loops that contains all the vertices of G...
    ...any idea?
  5. Apr 30, 2008 #4
    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: Apr 30, 2008
  6. Apr 30, 2008 #5
    Yes there should be no loops.
    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...
  7. Apr 30, 2008 #6
    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?
  8. May 1, 2008 #7
    Thanx anyway.
    I prooved it.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook