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
Best Answer
The proof is actually very simple, knowing these two facts:
If a tree has $|V|$ vertices, then it has $|V|-1$ edges. This is proved easily by induction.
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.