Question

Show that in a tree if degree of every non pendant vertex is 3 then number of vertices in tree is even

Answer 1

In a tree if degree of every non pendant vertex is 3 then number of vertices in tree is even.

• Lemma: At most one other non-pendant vertex is consequent to a non-pendant vertex that is present.
• Proof: If all the pendant vertices are removed, a tree that must contain at least one pendant vertex remains (made up of all the formerly non-pendant vertices).
• We will now infer the quantity of non-dependent vertices. Base case: dd incident pendant vertices at one non-pendant vertex. Choose a non-pendant vertex that is incident to no more than one other non-pendant vertex using the lemma in the inductive case. It contains incident pendant vertices of at least d - 1 and degree at least d. It becomes a pendant vertex when all of its pendant vertices are removed.
• The resulting tree has at least d pendant vertices according to the inductive hypothesis because it has one less non-pendant vertices. Returning to the original tree, we can see that we have at least d-1+(d-1) which is greater than equal to d pendent vertices.

Hence, in a tree if degree of every non pendant vertex is 3 then number of vertices in tree is even.

Learn more here

https://brainly.in/question/45525251

#SPJ1