Graph Theory - Spanning trees

1. Mar 25, 2012

Gh0stZA

Hi everyone,

Any help would be appreciated.

2. Mar 25, 2012

Max.Planck

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.

3. Mar 25, 2012

Gh0stZA

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?

4. Mar 25, 2012

Max.Planck

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.

5. Mar 25, 2012

Gh0stZA

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.

6. Mar 25, 2012

Max.Planck

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:

• counterexample.png
File size:
1.5 KB
Views:
127
7. Mar 25, 2012

Gh0stZA

Every spanning tree, I'm afraid. But isn't it a subgraph? Just not induced?

8. Mar 25, 2012

Max.Planck

Subgraph:
Definition: A graph whose vertices and edges are subsets of another graph.

9. Mar 25, 2012

Gh0stZA

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.)

10. Mar 25, 2012

Max.Planck

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.

11. Mar 25, 2012

Gh0stZA

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?

12. Mar 25, 2012

Max.Planck

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?

13. Mar 25, 2012

Gh0stZA

Graphs & Digraphs, 5th edition. By Chartrand & Lesniak.

14. Mar 25, 2012

Max.Planck

15. Mar 25, 2012

Gh0stZA

16. Mar 25, 2012