INDEPENDENCE AND THE HAVEL-HAKIMI RESIDUE

Favaron et al. (1991) have obtained a proof of a conjecture of Fajtlowicz' computer program Graffiti that for every graph G the number of zeroes left after fully reducing the degree sequence as in the Havel-Hakimi Theorem is at most the independence number of G. In this paper we present a simplified version of the proof of Graffiti's conjecture, and we find how the residue relates to a natural greedy algorithm for constructing large independent sets in G.