graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, the term bipartite hypergraph describes several related classes of

hypergraph In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices. Formally, an undirected hypergraph H is a pair H = (X,E) ...

s, all of which are natural generalizations of a

bipartite graph In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V ar ...

Property B and 2-colorability

The weakest definition of bipartiteness is also called 2-colorability. A hypergraph ''H'' = (''V'', ''E'') is called 2-colorable if its vertex set ''V'' can be partitioned into two sets, ''X'' and ''Y'', such that each hyperedge meets both ''X'' and ''Y''. Equivalently, the vertices of ''H'' can be 2-colored so that no hyperedge is monochromatic. Every bipartite graph ''G'' = (''X''+''Y'', ''E'') is 2-colorable: each edge contains exactly one vertex of ''X'' and one vertex of ''Y'', so e.g. ''X'' can be colored blue and ''Y'' can be colored yellow and no edge is monochromatic. The property of 2-colorability was first introduced by Felix Bernstein in the context of set families; therefore it is also called

Property B In mathematics, Property B is a certain set theoretic property. Formally, given a finite set ''X'', a collection ''C'' of subsets of ''X'' has Property B if we can partition ''X'' into two disjoint subsets ''Y'' and ''Z'' such that every set in ' ...

Exact 2-colorability

A stronger definition of bipartiteness is: a hypergraph is called bipartite if its vertex set ''V'' can be partitioned into two sets, ''X'' and ''Y'', such that each hyperedge contains ''exactly one'' element of ''X'' and ''exactly one'' element of ''Y''. Every bipartite graph is also a bipartite hypergraph. Every bipartite hypergraph is 2-colorable, but bipartiteness is stronger than 2-colorability. Let ''H'' be a hypergraph on the vertices with the following hyperedges:

This ''H'' is 2-colorable, for example by the partition ''X'' = and ''Y'' = . However, it is not bipartite, since every set ''X'' with one element has an empty intersection with one hyperedge, and every set ''X'' with two or more elements has an intersection of size 2 or more with at least two hyperedges.