The maximum weighted independent set for a tree can found out using the following dynamic programming approach.
Min[u] = wt(u) + Σ Mout[v] where v ∈ children(u) Mout[u] = Σ max { Min[v], Mout[v] } where v ∈ children(u)
where Min[u] and Mout[u] computes the total weight of the maximum independent set for the sub tree rooted at u by including or excluding u respectively.
I tried to proof the correctness of this algorithm. Suppose the independent set ( say I ) generated from this algorithm is not of maximum weight. Let the maximum weighted independent be I'. Then there must be a vertex V'∈ I' and V' ∉ I. And also there can be 2 cases. Either parent(V')∈ I or parent(V') ∉ I. I tried both the cases to solve furthur but could not proceed. Is this approach correct or there is some alternative way to prove the correctness.