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

Click For Summary
SUMMARY

The discussion centers on the proof that a subgraph F of a connected graph G is a subgraph of every spanning tree of G if and only if F contains no cycles. The participants explore two main implications: first, that if F is a subgraph of every spanning tree, then F must be acyclic; and second, that if F is acyclic, it must be a subgraph of every spanning tree. The conversation highlights the importance of understanding the definitions of spanning trees and subgraphs, as well as the implications of acyclicity in graph theory.

PREREQUISITES
  • Understanding of graph theory concepts, specifically spanning trees and subgraphs.
  • Familiarity with the definitions of acyclic graphs and their properties.
  • Knowledge of proof techniques, including proof by contradiction.
  • Ability to analyze isomorphic graphs and their relationships.
NEXT STEPS
  • Study the properties of spanning trees in connected graphs.
  • Learn about acyclic graphs and their significance in graph theory.
  • Explore proof techniques in mathematics, focusing on proof by contradiction.
  • Investigate the concept of isomorphism in graphs and its implications for subgraphs.
USEFUL FOR

This discussion is beneficial for students and professionals in mathematics, particularly those studying graph theory, as well as computer scientists and algorithm developers working with graph algorithms.

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: 625
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

MHB Graphs with N Nodes: Proving Cliques and Anti-Cliques
  • · Replies 6 ·
Replies
6
Views
3K
Minimum Size of Connected Subgraph in Graph Theory | Help with u and v in G
  • · Replies 11 ·
Replies
11
Views
5K
Graph theory - complete subgraphs
  • · Replies 1 ·
Replies
1
Views
3K
MHB Another tree-related graph theory proof
  • · Replies 1 ·
Replies
1
Views
2K
MHB Problem on Graph Theory and Algorithms
  • · Replies 2 ·
Replies
2
Views
3K
Easy proof about spanning trees (for you)
  • · Replies 5 ·
Replies
5
Views
2K
MHB Understanding Two Graph Theory Problems
  • · Replies 2 ·
Replies
2
Views
2K
How to Prove the Existence of a Cycle Subgraph for k-Connected Graphs?
  • · Replies 2 ·
Replies
2
Views
4K
MHB Graph theory proof related to trees
  • · Replies 1 ·
Replies
1
Views
2K
Graduate Every graph GG containing a cycle satisfies g(G)≤2d+1
  • · Replies 10 ·
Replies
10
Views
3K