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

In summary, the conversation discusses the proof of F being a subgraph of every spanning tree of a connected graph G, if and only if F contains no cycles. The conversation explores possible proofs and counterexamples, ultimately concluding that the assertion is false since F does not have to be a spanning tree itself. The conversation also provides a reference to a book discussing the topic.
  • #1
Gh0stZA
25
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
  • #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.
 
  • #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?
 
  • #4
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.
 
  • #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.
 
  • #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?
 

Attachments

  • counterexample.png
    counterexample.png
    1.3 KB · Views: 532
  • #7
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?
 
  • #8
Subgraph:
Definition: A graph whose vertices and edges are subsets of another graph.
 
  • #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.)
 
  • #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.
 
  • #16

1. What is a spanning tree in graph theory?

A spanning tree in graph theory is a subgraph of a connected, undirected graph that contains all of the vertices of the original graph and is also a tree (meaning it has no cycles). It is a way of representing the structure of a graph while minimizing the number of edges and ensuring that all vertices are connected.

2. How is a spanning tree different from a minimum spanning tree?

A minimum spanning tree is a spanning tree that has the minimum possible total weight of all its edges. In other words, it is the spanning tree that connects all vertices of a graph with the least possible cost. Not all spanning trees are minimum spanning trees, but all minimum spanning trees are spanning trees.

3. Why is finding a minimum spanning tree important?

Finding a minimum spanning tree is important because it can help us solve many practical problems, such as finding the most efficient way to connect a network of cities or the most cost-effective way to lay out a power grid. It also has applications in computer science, such as in designing efficient routing algorithms.

4. What are some algorithms used to find a minimum spanning tree?

Some commonly used algorithms for finding a minimum spanning tree include Prim's algorithm, Kruskal's algorithm, and Boruvka's algorithm. These algorithms differ in their approach but all aim to find the minimum spanning tree of a graph by considering the weights of its edges.

5. Can a graph have more than one minimum spanning tree?

Yes, a graph can have more than one minimum spanning tree. If there are multiple edges with the same weight in a graph, then there can be multiple minimum spanning trees with different edge combinations. However, all of these trees will have the same total weight and will still be considered minimum spanning trees.

Similar threads

MHB Chordal graphs and perfect elimination orderings
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
MHB Graphs with N Nodes: Proving Cliques and Anti-Cliques
    • Set Theory, Logic, Probability, Statistics
Replies
6
Views
2K
MHB Understanding Two Graph Theory Problems
    • Set Theory, Logic, Probability, Statistics
Replies
2
Views
2K
Minimum Size of Connected Subgraph in Graph Theory | Help with u and v in G
    • Set Theory, Logic, Probability, Statistics
Replies
11
Views
4K
Easy proof about spanning trees (for you)
    • Engineering and Comp Sci Homework Help
Replies
5
Views
1K
MHB Another tree-related graph theory proof
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
Graph theory - complete subgraphs
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
2K
A Every graph GG containing a cycle satisfies g(G)≤2d+1
    • General Math
Replies
10
Views
2K
MHB Problem on Graph Theory and Algorithms
    • Set Theory, Logic, Probability, Statistics
Replies
2
Views
2K
MHB Graph theory proof related to trees
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K

Hot Threads

Recent Insights

Back
Top