If a graph has less then $2n$ vertices, then it can't have $n$ spanning trees such that each pair is edge disjoint
This must apply for $n\geq 3$
I am not sure how to prove this.
Probably the best way is via contradiction: Prove that if is has less then $2n$ vertices, that it can have $n$ spanning trees such that each pair is edge disjoint, and find a contradiction.
The max number of nodes in a undirected graph is $a(a-1)/2$, and so in our case it is $2n(2n-1)/2=n(2n-1)$
We know that to be a spanning tree, you must use edges = number of vertices – 1.
So in our case, spanning trees must use $2n-1$ edges.
Since I want $n$ spanning trees, that is also $n(2n-1)$ edges.
What I want to do is compare these two and arrive at a contraidction, but am stuck here.
Best Answer
Let $|V|=v < 2n$ be the number of vertices of your graph. Assume that it has $n$ spanning trees, pairwise edge disjoint.
Any spanning tree must have $v-1$ edges. If all $n$ trees are pairwise edge disjoint, then you graph must have at least $n(v-1)$ edges. $$ |E| \geq n(v-1)$$
However, using $n >\frac{v}{2}$
$$ |E| \geq n(v-1) > \frac{v(v-1)}{2}=e_\max$$ With $e_\max$ the maximum number of edge of a graph on $v$ vertices ($K_v$). Therefore this is a contradiction.