又一道。。。。。。how to prove that a tree with v vertices has v-1 edges?
induction
if v=1, then e=0. ture.
assume the statement is true for v<=k, (k>=1).
for v=k+1, we can always find a leaf, remove it, and the edge it connect to. then v-1 verteices and e-1 edges left. from assumption, (e-1)=(v-1)-1, or e=v-1.
assume the statement is true for v<=k, (k>=1).
for v=k+1, we can always find a leaf, remove it, and the edge it connect to. then v-1 verteices and e-1 edges left. from assumption, (e-1)=(v-1)-1, or e=v-1.
Huasing Association 1999 - 2013