Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Graph Theory - Spanning trees

  1. Mar 25, 2012 #1
    Hi everyone,

    Any help would be appreciated.
     
  2. jcsd
  3. Mar 25, 2012 #2
    This is what you need to prove:

    1. F is a subgraph of every ST of G implies F contains no cycles

    and

    2. F contains no cycles implies F is a subgraph of every ST of G

    You can try a proof by contradiction so in proof 1 it will be:
    Assume F is a subgraph of every ST of G and F contains a cycle.
    But if F contains a cycle then F is not a spanning tree. But then F cannot be
    subgraph of a spanning tree, so 1 must be true.

    Ill let you do 2.
     
  4. Mar 25, 2012 #3
    Hi Max.Planck,

    Thanks for the boost. The first one is simple enough, but I'm just wondering about the second one...

    For (2):
    F is a subgraph of G. We assume that F is acyclic.

    If F is disconnected, then F is not a ST and cannot be a subgraph of one.

    If F is connected, and of course acyclic, it is a tree and a subgraph of G also. Since the spanning trees of G contain every vertex of G, F can either be contained in the spanning tree or it is in itself a spanning tree.

    Would this suffice?
     
  5. Mar 25, 2012 #4
    This statement is false, even if it is not connected, it can still be (and will be if it is acyclic) a subgraph of a spanning tree.

    I think your second statement is a valid point.
     
  6. Mar 25, 2012 #5
    Okay, let's try it this way?

    If F is connected, and acyclic, it is a tree and also a subgraph of G. Since every spanning tree of G contains all the vertices of G, F must be contained in the spanning trees of G, or is in itself a spanning tree.

    If F is disconnected, but acyclic, all the vertices of F are still contained in the spanning trees of G, and F is a subgraph of the spanning trees of G.
     
  7. Mar 25, 2012 #6
    Wait, I might have found a counterexample.
    Look at this graph G. Now the graph on the right is a spanning tree of G. The one on the bottom is acyclic, however it is not a subgraph of the one on the right. Are you sure you had to prove it was a subgraph of every spanning tree or a spanning tree?
     

    Attached Files:

  8. Mar 25, 2012 #7
    Every spanning tree, I'm afraid. But isn't it a subgraph? Just not induced?
     
  9. Mar 25, 2012 #8
    Subgraph:
    Definition: A graph whose vertices and edges are subsets of another graph.
     
  10. Mar 25, 2012 #9
    Okay, would it help knowing the spanning trees are isomorphic to one another? Just guessing? Or if we only say there exists some F, for example, the edge 2_3 in your picture, such that it is a subgraph of every spanning tree? (I mean even if there is just 1 vertex in common, K_1 is still a subgraph and a tree.)
     
  11. Mar 25, 2012 #10
    The graphs are isomorphic yes, but I don't think they are subgraphs of each other. So the assertion is false, since 2 is not true.
     
  12. Mar 25, 2012 #11
    Okay but since F doesn't have to be a spanning tree in itself, isn't it possible to find, say, just 1 vertex that will be a subgraph of every spanning tree? A complete graph of order 1 or even 2, that will be a subgraph of every spanning tree, if you understand what I'm saying?
     
  13. Mar 25, 2012 #12
    Of course, but the premise was "F is an acyclic graph which is a subgraph of G". The graph on the right satisfies this property, however it is not a subgraph of the graph below, but the graph below IS a spanning graph of G. Where did you get this problem by the way?
     
  14. Mar 25, 2012 #13
    Graphs & Digraphs, 5th edition. By Chartrand & Lesniak.
     
  15. Mar 25, 2012 #14
  16. Mar 25, 2012 #15
  17. Mar 25, 2012 #16
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Graph Theory - Spanning trees
  1. Graph Theory (Replies: 1)

  2. Graph Theory Question (Replies: 2)

Loading...