Is F a Subgraph of Every Spanning Tree of G If It Contains No Cycles?

Gh0stZA
Messages
25
Reaction score
0
Hi everyone,

Let F be a subgraph of a connected graph G. Prove that F is a subgraph of every spanning tree of G iff F contains no cycles.

Any help would be appreciated.
 
Physics news on Phys.org
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.
 
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?
 
Gh0stZA said:
Hi Max.Planck,

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

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

Attachments

  • counterexample.png
    counterexample.png
    1.3 KB · Views: 602
Max.Planck said:
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?

Every spanning tree, I'm afraid. But isn't it a subgraph? Just not induced?
 
Subgraph:
Definition: A graph whose vertices and edges are subsets of another graph.
 
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
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
Max.Planck said:
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.

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
Gh0stZA said:
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?

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
Max.Planck said:
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?

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

Similar threads

Replies
1
Views
2K
Replies
1
Views
2K
Replies
2
Views
3K
Replies
5
Views
2K
Replies
2
Views
2K
Replies
1
Views
2K
Back
Top