# Let $G$ be a graph with $2$ spanning trees.

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

Now we try $$K_4$$ Now I'm just trying to find if any two trees can be disjoint

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

• 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. – bof Feb 20 at 3:04

## 1 Answer

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.

• 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". – bof Feb 20 at 2:56