Could you help with Question 4: algorithm/pseudocode and time complexity if poss

Question

Could you help with Question 4: algorithm/pseudocode and time complexity if possible.

Question 4: 1. Consider a tree T(V. E) with n > 2 vertices. Show that PET deg(v) 2n-1 2. Say that we are given n numbers di, d2,...,dn so that 2n 1. Show that at least two of the numbers have value 1. 3. Prove that at least one value of the di above is at least 2 4. Prove by induction that if we are given n num bers d1, d2, . . . , dn so that ?-1- 2n- 1 there is a tree T(V, E) with vertices v, Un so that deg(v:)d Hint: Remove a number d, of value 1 (it exists. See above). After the removal use the fact that there is a number di that is at least 2. Change di to di -1. Apply the induction hypothesis, on the n - 1 new numbers (there are n -1 numbers since we remove a number of value 1 from the set of numbers). The number 1 that we removed needs to be a leaf (to have degree 1) because di 1. The last step is adding back a leaf. But recall that the degree of di is di 1 in the induction tree. Question 5:

Explanation / Answer

1. With n vertex there will be n-1 edges

Each edge will contribute to 2 degree.

total degree = 2(n-1)

Question seems incorrect.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---