# Proving that any two spanning trees for a graph has the same number of edges

Prove that any two spanning trees for a graph has the same number of edges.

Proving by contradiction. Assume that there exists two spanning trees with different number of edges.

Take $G$ to be the original graph with $n$ number of edges. A spanning tree/ subgraph $H$ is obtained from $G$ by removing one edge from $G$ thus giving $n-1$ edges

while another spanning tree/ subgraph $B$ is obtained from $G$ by removing two edges from $G$ thus giving $n-2$ edges.

And since $H$ is a spanning tree with $n-1$ edges $H$ cannot have any circuit. And thus $n-1$ is the minimmum number of edges to form a tree.(Ie removing any more edges will not give a connected graph) Thus we know that graph $B$ with $n-2$ edges cannot form a tree, thus a contradiction. Im getting the idea but could anyone improve on my proof and explain whether is it correct. Thanks

• I don't get how your argument works. – Crostul Apr 24 '16 at 9:43

The proof is actually very simple, knowing these two facts:

1. If a tree has $|V|$ vertices, then it has $|V|-1$ edges. This is proved easily by induction.

2. If $G$ is a connected graph with $|V|$ vertices, and $T$ is a spanning tree of $G$, then the set of vertices of $T$ coincides with the set of vertices of $G$ (this is the definition of spanning tree). In particular, $T$ has $|V|$ vertices.

From these two facts, you have that any spanning tree must have exactly $|V|-1$ edges.

• Yup my main idea is that ,Assuming that there exists two spanning trees with different number of edges. and that one of them have $V-1$ edges then the other cannot have $V-1$ edges thus a contradiction. – ys wong Apr 24 '16 at 9:50
• Well, you don't need contradiction here. Any two spanning trees have $|V|-1$ edges, hence they have the same number of edges (which is $|V|-1$). – Crostul Apr 24 '16 at 9:51