  The notion of augmenting graphs generalizes Berge's idea of augmenting
chains, which was used by Edmonds in his celebrated solution of the maximum
matching problem. This problem is a special case of the more general maximum
independent set (MIS) problem. Recently, the augmenting graph approach has been
successfully applied to solve MIS in various other special cases. However, our
knowledge of augmenting graphs is still very limited, and we do not even know
what the minimal infinite classes of augmenting graphs are. In the present
paper, we find an answer to this question and apply it to extend the area of
polynomial-time solvability of the maximum independent set problem.
