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?

  • 1
    $\begingroup$ 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. $\endgroup$ – brick Nov 5 '14 at 0:27
  • $\begingroup$ @brick What is the recursive definition of a tree? $\endgroup$ – user142198 Nov 5 '14 at 0:51
  • $\begingroup$ 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. $\endgroup$ – brick Nov 5 '14 at 23:21
  • $\begingroup$ @brick That makes sense. Thank you $\endgroup$ – user142198 Nov 5 '14 at 23:38
  • 1
    $\begingroup$ you're welcome :) $\endgroup$ – brick Nov 5 '14 at 23:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy