The box-TDI system associated with 2-edge connected spanning subgraphs

AbstractLet G be a graph and let A be its cutset-edge incidence matrix. We prove that the linear system 12Ax≥1,x≥0 is box totally dual integral (box-TDI) if and only if G is a series-parallel graph; a by-product of this characterization is a structural description of a box-TDI system on matroids. Our results strengthen two previous theorems obtained respectively by Cornuéjols, Fonlupt, and Naddef and by Mahjoub which assert that both polyhedra {x∣12Ax≥1,x≥0} and {x∣12Ax≥1,1≥x≥0} are integral if G is series-parallel