On the integrality of an extreme solution to pluperfect graph and balanced systems

Let A be a nonnegative integer matrix, and let e denote the vector all of whose components are equal to 1. The pluperfect graph theorem states that if for all integer vectors b the optimal objective value of the linear program minse′xvbAx ? b, x ? 0 s is integer, then those linear programs possess optimal integer solutions. We strengthen this theorem and show that any lexicomaximal optimal solution to the above linear program (under any arbitrary ordering of the variables) is integral and an extreme point of sxvbAx ? b, x ? 0 s. We note that this extremality property of integer solutions is also shared by covering as well as packing problems defined by a balanced matrix A.