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|².