Recent content by Gh0stZA

  1. G

    Graph Theory - Connectivity of r-regular graphs

    Sorry for the bump, any ideas on this?
  2. G

    Graph Theory - Connectivity of r-regular graphs

    Hello everyone. All help appreciated.
  3. G

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

    Just to prove that I am not insane... ;) http://hashcookie.net/uploads/3da35b5ad0_chartrandlesniak.png But I agree with you, and thank you very much for your help.
  4. G

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

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

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

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

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

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

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

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

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

    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...
  9. G

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

    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...
  10. G

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

    Hi everyone, Any help would be appreciated.
  11. G

    Graph theory - complete subgraphs

    Sorry to bump, any help please?
  12. G

    Graph theory - complete subgraphs

    Hi everyone. I know this holds for complete graphs, I've proved that by induction. But how can I prove it for graphs which aren't complete? And what is the significance of (2n+1)/3? If a vertex has that degree, does it have some property I should immediately spot?
  13. G

    Cardinalities of power set vs B^A

    I think I understand this concept now. The notation is still a little new to me and I haven't done a lot of "pure" set theory before, especially not recently, but I think I got the basic idea from this. Thanks guys.
  14. G

    Cardinalities of power set vs B^A

    Can you please elaborate on this?
  15. G

    Cardinalities of power set vs B^A

    Hi everyone, If B^A is the set of functions mapping from A \rightarrow B = \{ 0, 1 \}, prove that |B^A| = |P(A)|, where P(A) is the power set of A. Is it as simple as letting the mapping from B to A be denoted by \phi and defining a_1, a_2 \in A, a_1 \ne a_2 such that \phi (a_1) = 0 and...
Back
Top