  The Nemhauser-Trotter theorem states that the standard linear programming
(LP) formulation for the stable set problem has a remarkable property, also
known as (weak) persistency: for every optimal LP solution that assigns integer
values to some variables, there exists an optimal integer solution in which
these variables retain the same values. While the standard LP is defined by
only non-negativity and edge constraints, a variety of other LP formulations
have been studied and one may wonder whether any of them has this property as
well. We show that any other formulation that satisfies mild conditions cannot
have the persistency property on all graphs, unless it is always equal to the
stable set polytope.
