# 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

• 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