Recall that we showed in class that if T is a tree with least 2 vertices, then T contains a leaf. (A
leaf is a vertex of degree one.) Recall also that if T is a tree with leaf x, then T − x is also a tree. (Here,
T − x denotes the tree obtained by deleting x and the edge incident to x from T .)
Prove by induction that if T is a tree, then the number of edges of T is one less than the number of
vertices of T .
(Hint: To start, let P(n) be the proposition that every tree with n vertices has n − 1 edges.)

Hey! We 've verified this expert answer for you, click below to unlock the details :)

I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!

what do you mean? is the function p(n)=n-1?

What definition of tree would you like to use?

Looking for something else?

Not the answer you are looking for? Search for more explanations.

## More answers

Looking for something else?

Not the answer you are looking for? Search for more explanations.