1
$\begingroup$

Suppose I have a simple, planar graph, which I want to partition into three edge sets such that each set forms a spanning tree. I've made an attempt at a solution, but it requires a few assumptions that I'm not sure I can make; here's what I've got so far:

Let's say we have a tree with n nodes; then that tree must have n-1 edges. [[ASSUMPTION: All possible spanning trees of a graph must have an equal number of nodes, and, those spanning trees must not be disjointed.]] Thus, given that the graph is both simple and planar, and assuming that we can partition the graph into three edge sets such that each set forms a spanning tree, then we can say that the graph has at most 3n-6 edges. Then if we create three equal partitions, each edge set can have at most n-2 edges, and there is no way to partition the graph so that ALL three sets have greater than n-2 edges, which is what we need to make every set a spanning tree of the graph (given that they must have n-1 edges).

I'm not quite sure though how I can make the leaps that: 1) All spanning trees in the graph must have a an equal number of nodes (though intuitively, this makes sense to me). 2) If a graph has multiple spanning sets within it, those sets are necessarily not disjointed. (I'm less intuitively sure of this one, and that's probably not a good way to approach the problem, but it seems possible, only I'm not sure how to prove it, but it's all I've got so far.)

$\endgroup$
0
$\begingroup$

For "All spanning trees in the graph must have an equal number of nodes" -- consider what it means to be a spanning subgraph.

I can't tell what you mean by "If a graph has multiple spanning sets within it, those sets are necessarily not disjointed."

$\endgroup$
  • $\begingroup$ For the second part, I mean that every spanning tree in the graph must intersect - at the nodes - with every other spanning tree in the graph - but I suppose this follows from what you already mentioned? That is, what it means to be a spanning tree, which, in particular, means that all the nodes of the graph are contained within the spanning tree, only that the edges are different. But I think I just answered my own question, if I'm not mistaken. $\endgroup$ – cerremony Nov 27 '14 at 18:52
  • $\begingroup$ Yes, I think you pretty much have. $\endgroup$ – Gregory J. Puleo Nov 27 '14 at 18:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.