Theorem 4.4 Every tree of order n bas size n-1. Proof.We proceed by induction on n. There is only one tree of order 1,namely K1,which has size 0.Thus the result is true for n=1. Assume for a positive integer k that the size of every tree of order k is k-1. Let Tbe a tree of order k+1.By Theorem 4.3,T contains at least two end-vertices.Let v be one of them.Then T=T-v is a tree of order k.By the induction hypothesis,the size of T'is m =k-1. Since Thas exactly one more edge than T,the size of Tis m+1 (k-1)+1=(k+1)-1,as desired.Theorem 4.4 Every tree of order n has size n − 1. ◼ Proof. We proceed by induction on n. ❑ There is only one tree of order 1, namely K1 , which has size 0. Thus the result is true for n = 1. ❑ Assume for a positive integer k that the size of every tree of order k is k − 1. ❑ Let T be a tree of order k + 1. By Theorem 4.3, T contains at least two end-vertices. Let v be one of them. Then T′ = T − v is a tree of order k. By the induction hypothesis, the size of T′ is m = k − 1. Since T has exactly one more edge than T′, the size of T is m + 1 = (k − 1) + 1 = (k + 1) − 1, as desired