Maximum independent set in a tree. Review algorithm, need proof

Question

pseudocode:

void recursive('k'){ // 'k' and 'i' vertices
  sumA = 0;
  sumB = 0;
  for each non visited 'i' neighbor do{
     recursive('i');
     sumA = sumA + b['i'];
     sumB = sumB + max(a['i'], b['i']);
     }
  a['k'] = 1 + sumA;
  b['k'] = sumB;
  }


void main(){
 a = b = 0; //initialize tables with 0 (zeros)
 recursive('X');  //let 'X' be an arbitrary root
 cout<<max(a['X'], b['X']);
 }

need proof that max(a['X'], b['X']) is the cardinal of the maximum independent set in the tree. What am I missing ?

Thank you in advance.

Answer 1

The element a[i] is the size of the maximal independent set in the subtree rooted in i which contains i.

The element b[i] is the size of the maximal independent set in the subtree rooted in i which doesn't contain i.

The algorithm computes these recursively, and then chooses the maximal of the two at the root.