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.)

Question

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.)

thomas5267 · Answer

What is the definition of tree?  If the definition of the tree is chosen to be a connected graph with n vertices and n-1 edges, then the proof is trivial.  If the definition of the tree is chosen to be a connected graph with no cycles, then the proof is slightly more complicated.

bee_see · Answer

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

thomas5267 · Answer

What definition of tree would you like to use?

bee_see · Answer

It's fine. I was able to solve the problem.