# Proof verification that two spanning tress of the same graph are the same size

Let $H$ be any graph and $T_1$ and $T_2$ be spanning trees for $H$. Prove that the size of $T_1$ equals the size of $T_2$.

Proof: $T_1$ has an edge set $\{\{v_1,v_2\},\{v_2,v_3\},\dots,\{v_{n-1},v_n\}\}$ which has $n-1$ elements.

$T_2$ has an isomorphic labelling, $\{\{v_1,v_2\},\{v_2,v_3\},.\dots,\{v_{m-1},v_{m}\}\}$ which has $m-1$ elements where $m$ and $n$ are the final vertices, and hence $m=n$.

Thus both trees are of the same size.

Critique? Is this even a valid proof?

• Every tree with $n$ vertices has exactly $n-1$ edges. That can be proved by induction using the recursive definition of a tree. It should be easy I guess. – brick Nov 5 '14 at 0:27
• @brick What is the recursive definition of a tree? – user142198 Nov 5 '14 at 0:51
• 1) A single node without any edges is a tree. And 2) if $A$ and $B$ are trees and you connect a vertex from $A$ and a vertex from $B$ you get a tree again. All of the trees can be constructed using these $2$ rules. – brick Nov 5 '14 at 23:21
• @brick That makes sense. Thank you – user142198 Nov 5 '14 at 23:38
• you're welcome :) – brick Nov 5 '14 at 23:40