Critical Cutsets of Graphs and Canonical Facets of Set-Packing Polytopes

A cutset in a graph G with node set N is the set of edges joining the nodes in a subset of N to those not in the subset. We call a cutset critical if its removal produces a graph whose independence number is greater than that of G. We use the concept of a critical cutset to give first a necessary, then a sufficient condition for an inequality with 0–1 coefficients to be a facet of the set-packing polytope defined by G.