On the connectedness of optimum-degeneracy graphs

So-called optimum-degeneracy graphs describe the structure of the set of primal and dual feasible bases associated with a degenerate vertex of the feasible solution set of a linear program. The structural properties of these graphs play an important role in determining shadow prices or performing sensitivity analysis in linear programming under degeneracy. We prove that general optimum-degeneracy graphs are connected and that negative optimum-degeneracy graphs are connected under certain conditions.