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!

Spanning tree question

  1. May 14, 2005 #1
    I'm trying to prove the following theorem using graph theory:

    I first tried to come up with an example:

    Graph G
    Vertices: a, b, c, d.
    Edges: ab, ac, ad, bc, cd.

    Spanning tree T
    Vertices: a, b, c, d.
    Edges: ab, ac, ad. (x = ac)

    Spanning tree T'
    Vertices: a, b, c, d.
    Edges: ad, cd, bc. (y = bc)

    Spanning tree (T - {x}) U {y}
    Vertices: a, b, c, d.
    Edges: [(ab, ac, ad) - (ac)] U bc = ab, ad, bc.
    Which is really a spanning tree.

    Spanning tree (T' - {y}) U {x}
    Vertices: a, b, c, d.
    Edges: [(ad, cd, bc) - bc] U ac = ad, cd, ac.
    But this is a cycle that leaves b apart, not a spanning tree!

    What did I do wrong?


  2. jcsd
  3. May 14, 2005 #2
    are you sure the question says prove: or is it prove/disprove?
  4. May 14, 2005 #3
    If I recall correctly the theorem should be that given an x in the edge set of T but not in the edge set of T' then there exists a y in the edge set of T' that is not in the edge set of T such that ... (same conclusion)

    so the y depends on x

    Though I haven't looked this up... this is just my vague recollection
  5. May 14, 2005 #4
    Yes, I'm sure. The question asks me to prove the theorem.
  6. May 14, 2005 #5
    I guess you're right: the theorem also says that, if there is an edge x in T, but not in T', then there is an edge y which is in T', but not in T. But I guess my first example follows this as well: x = ac is an edge that belongs to T, but not to T'; then there must be an edge y that belongs to T', but not to T. In my example, y = bc. Am I missing anything?
  7. May 14, 2005 #6
    OK, I guess I figured it out. I misunderstood the theorem. I'll try to restate it:

    What I understand is that, if there is x, then there must be at least one y that follows the theorem. In other words, not every edge that belongs to T' but not to T is the y that the theorem wants. In my example, bc is not good to be y. I could, however, choose x = ac and y = ad, finding the following spanning trees:

    - ab, ad, bc
    - ac, bc, dc

    Is this right?
  8. May 14, 2005 #7
    I believe that's the right idea. Of course proving it is a bit more of a challenge.
  9. May 14, 2005 #8

    I don't know if this will work, but could you do something like this:

    Given spanning trees T and T', take an edge, x, in T that connects U to V that is not in T'.

    Since x was the bridge from U to V, to re-create a tree, we have to replace it.

    In T' there was also a U-V path, because in trees all vertices have to be connected, but we can also not duplicate any other path in the tree or create a circuit because the end result also has to be a tree...

    So the problem lies in re-building that bridge.

    What I am thinking is, can you say that you'll add the path without duplicating it because T and T' are not the same tree???

    We did have that to begin with? Or not?

    I'm not sure if maybe you could say use an algorithm to create a tree but avoid using that initial branch?

    Another thing I'm thinking is maybe you could say that if you add the edge from the other tree, you will create a circuit so there are 2 paths from U to V, then break the circuit by taking out the original x from T and you will still have a tree.

    I don't know if either of these approaches will work for you, tell me what you think.

    - Vanes.
  10. May 14, 2005 #9
    ah for the restated question it is a simple PROOF (10-15min)

    the question is about disconnected graphs and parity.
    [1]T -{x} = ?
    [2]T'+{x} = ?
    Apply parity of [1] on what you can think of for [2]

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook