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