  We introduce multiple symmetric LP relaxations for minimum cut problems. The
relaxations give optimal and approximate solutions when the input is a
Hamiltonian cycle. We show that this leads to one of two interesting results.
In one case, these LPs always give optimal and near optimal solutions, and then
they would be the smallest known symmetric LPs for the problems considered.
Otherwise, these LP formulations give strictly better LP relaxations for the
traveling salesperson problem than the subtour relaxation. We have the smallest
known LP formulation that is a 9/8-approximation or better for min-cut. In
addition, the LP relaxation of min-cut investigated in this paper has
interesting constraints; the LP contains only a single typical min-cut
constraint and all other constraints are typically only used for max-cut
relaxations.
