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