15,882,464 members
See more:
Do the following inductive proof:

Let d1, d2, ..., dn, with n at least 2, be positive integers. Use mathematical induction to explain why, if d1+ d2+…+dn = 2n-2, then there must be a tree with n vertices whose degrees are exactly d1, d2, ..., dn. (Be careful with reading this statement. It is not the same as saying that any tree with vertex degrees d1, d2, ..., dn must satisfy d1+ d2+...+dn = 2n-2, although this is also true. Rather, it says that if you begin with the numbers d1, d2, ..., dn, then you can find such a tree.)
Posted
Updated 17-Sep-13 5:27am
v2
[no name] 17-Sep-13 11:18am
We are not going to do your homework for you.
Abhinav Chitre 17-Sep-13 11:23am
Its not homewrk! Its a Google Interview Question. and I thought people help here!
[no name] 17-Sep-13 11:26am
We do when you ask a question according to the guidelines. This is not even a question.
phil.o 17-Sep-13 12:24pm
Here we help who help themselves.
If you do not understand this question then you probably should not have this interview yet.

## Solution 1

We do not do your homework: it is set for a reason. It is there so that you think about what you have been told, and try to understand it. It is also there so that your tutor can identify areas where you are weak, and focus more attention on remedial action.

If it's an interview question, then how does us giving you answers help anybody? Would you be able to do the job any better if we did? No.

Try it yourself, you may find it is not as difficult as you think!