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