# If a graph has less then $2n$ vertices, then it can't have $n$ spanning trees such that each pair is edge disjoint

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.

• math.stackexchange.com/questions/1255057/… may be relevant. – Gerry Myerson Feb 15 at 3:06
• You say: "The max number of nodes in an undirected graph is $a(a-1)/2$." What is $a$? And what is a "node"? Are "nodes" edges or vertices or something else? – bof Feb 15 at 3:19
• $a$ is the number of nodes. Nodes and vertices are used interchangably here – K Split X Feb 15 at 3:33
• Note that the title says less than $2n$ vertices (well, actually, it says "less then", and it should say "fewer than", but never mind), while the reasoning allows as many as $2n$ vertices. So, which is it? Are $2n$ vertices allowed, or not? – Gerry Myerson Feb 15 at 9:01

## 1 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.