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

Click For Summary

Discussion Overview

The discussion revolves around the conditions under which a subgraph F of a connected graph G is a subgraph of every spanning tree of G, particularly focusing on the implications of F being acyclic. Participants explore the logical structure of the proof required to establish this relationship.

Discussion Character

  • Technical explanation
  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • Some participants propose that proving F is a subgraph of every spanning tree of G implies that F contains no cycles.
  • Others argue that if F contains no cycles, it must be a subgraph of every spanning tree of G, but question the implications if F is disconnected.
  • A participant suggests that an acyclic but disconnected F cannot be a spanning tree and raises concerns about its status as a subgraph of a spanning tree.
  • Counterexamples are introduced, where an acyclic graph is not a subgraph of a specific spanning tree, challenging the necessity of F being a subgraph of every spanning tree.
  • There is a discussion about the isomorphism of spanning trees and whether having a single vertex in common could qualify as a subgraph of every spanning tree.
  • Some participants reference a textbook that suggests the requirement might be for "some" spanning tree rather than "every" spanning tree, indicating a potential misinterpretation of the problem statement.

Areas of Agreement / Disagreement

Participants express differing views on whether F must be a subgraph of every spanning tree or if it suffices for F to be a subgraph of some spanning tree. The discussion remains unresolved regarding the implications of F being disconnected and the interpretation of the problem statement.

Contextual Notes

There are limitations in the discussion regarding the assumptions made about the connectivity of F and the definitions of subgraphs and spanning trees. The implications of the term "every" versus "some" spanning tree are also noted as a point of contention.

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

Graduate When can transitivity emerge from cycle-suppressing dynamics?
  • · Replies 1 ·
Replies
1
Views
483
MHB Graphs with N Nodes: Proving Cliques and Anti-Cliques
  • · Replies 6 ·
Replies
6
Views
3K
Graduate Minimum Size of Connected Subgraph in Graph Theory | Help with u and v in G
  • · Replies 11 ·
Replies
11
Views
5K
Graduate 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
Graduate 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