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.

  • $\begingroup$ math.stackexchange.com/questions/1255057/… may be relevant. $\endgroup$ – Gerry Myerson Feb 15 at 3:06
  • $\begingroup$ 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? $\endgroup$ – bof Feb 15 at 3:19
  • $\begingroup$ $a$ is the number of nodes. Nodes and vertices are used interchangably here $\endgroup$ – K Split X Feb 15 at 3:33
  • $\begingroup$ 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? $\endgroup$ – Gerry Myerson Feb 15 at 9:01

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.


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.