## Bipartite Subgraph Polytope

Contributed by Laura Galli and
Adam N. Letchford, expanded by Stefan Lörwald.
A set of edges of an undirected graph G is called bipartite, if it does not
contain the edge set of an odd cycle of G. The *Bipartite Subgraph
polytope BS(n)* is the convex hull of incidence vectors of bipartite
edge sets of a complete undirected graph on n nodes. See for example
A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Volume
C.

Note: A facet class is the orbit of the natural action of the symmetric
group *S(n)* on *BS(n)*. Only one representative of each
facet class is listed in the files.
### BS(4)

Status: complete description

3 classes

Vertices

Classes (node permutations) of facets

### BS(5)

Status: complete description

5 classes

Vertices

Classes (node permutations) of facets

### BS(6)

Status: complete description

6 classes

Vertices

Classes (node permutations) of facets

### BS(7)

Status: complete description

17 classes

Vertices

Classes (node permutations) of facets

### BS(8)

Status: complete description

85 classes (incomplete description, provided by L. Galli and A.N. Letchford, 2010)

171 classes (complete description, provided by S. Lörwald, 2014)

Vertices

### References

F. Barahona, M. Groetschel & A.R. Mahjoub (1985): Facets of the
bipartite subgraph polytope. Math. Oper. Res., 10, 340-358.

L. Galli & A.N. Letchford (2010): Small bipartite subgraph polytopes.
Working paper, Department of Management Science, Lancaster University.

Last modified: May 28, 2014 (SL)