I have researched the solution but I haven't founded yet. I know of course, a tree with n nodes must have exactly n-1 edges. But, I can't prove it.

equissupnica7

equissupnica7

Answered question

2022-07-16

Discrete math - Prove that a tree with n nodes must have exactly n 1 edges? I have researched the solution but I haven't founded yet. I know of course, a tree with n nodes must have exactly n 1 edges. But, I can't prove it.

Answer & Explanation

Carassial3

Carassial3

Beginner2022-07-17Added 9 answers

Step 1
It's easy to see that any tree with 1 node has 0 edges. Now let's assume that any tree with k nodes has k 1 edges. Now, given any tree with k + 1 nodes there must exist at least one leaf. Remove a leaf and the connecting edge.
Step 2
The resulting tree has k nodes and by our induction assumption it has k 1 edges. Hence, the tree with k + 1 nodes must have k edges. And from induction, we have the result.

Do you have a similar question?

Recalculate according to your conditions!

New Questions in Discrete math

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?