Some New Matroids on Graphs: Cut Sets and the Max Cut Problem

Abstract

We define some new matroids on the edge set of a graph. We show that minimal disconnecting edge sets and minimal edge sets which cover all the odd cycles are cocircuits of a binary matroid. We give a polynomial algorithm for finding a minimum weight circuit in our matroids. A necessary and sufficient condition for an edge set to be the minimum weight odd cycle cover is derived in terms of the family of cut sets of the graph.