Facets of the Bipartite Subgraph Polytope

The bipartite subgraph polytope P B (G) of a graph G = [V, E] is the convex hull of the incidence vectors of all edge sets of bipartite subgraphs of G. We show that all complete subgraphs of G of odd order and all so-called odd bicycle wheels contained in G induce facets of P B (G). Moreover, we describe several methods with which new facet defining inequalities of P B (G) can be constructed from known ones. Examples of these methods are contraction of node sets in odd complete subgraphs, odd subdivision of edges, certain splittings of nodes, and subdivision of all edges of a cut. Using these methods we can construct facet defining inequalities of P B (G) having coefficients of order |V| 2 .