0
$\begingroup$

Question) Let $G$ be a graph with $2$ spanning trees.


Now we try $K_4$

enter image description here

Now I'm just trying to find if any two trees can be disjoint

tree1:

enter image description here

enter image description here

managed to find two after writing them all down. Therefore the least number of edge-disjoint spanning trees is a graph of $4$ vertices.

Is this right?

Is there an easier way to show this? Mainly had trouble finding all the disjoint spanning trees

$\endgroup$
  • $\begingroup$ I guess you haven't covered "self-complementary graphs" yet. If you had, you would know that there is a self-complementary graph on $4$ vertices, and it is $P_4$. If you just know that there is a self-complementary graph on $4$ vertices, then you know that it's connected (every self-complementary graph is connected) and it has $\binom 42/2=3$ vertices, and a connected graph with $4$ vertices and $3$ edges is a tree. $\endgroup$ – bof Feb 20 at 3:04
1
$\begingroup$

That should be totally fine. You checked all possibilities. Actually this is the easiest method in my opinion, but if someone knows an even easier one, I'd be interested in it.

$\endgroup$
  • 1
    $\begingroup$ A spanning tree has $n-1$ edges, and $$2(n-1)\le\binom n2\implies n=1\text{ or }n\ge4$$ but this is hardly easier than checking $n=2$ and $n=3$ by hand. By the way, doesn't $K_1$ have two edge-disjoint spanning trees? I gues it depends on what you mean by "two". $\endgroup$ – bof Feb 20 at 2:56

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.