In graph theory, the term bipartite hypergraph describes several related classes of hypergraphs, all of which are natural generalizations of a bipartite graph.
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.
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.
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.
A stronger definition is: given an integer n, a hypergraph is called n-uniform if all its hyperedges contain exactly n vertices.
Let H be the hypergraph:[citation needed]{ {1,2} , {3,4} , {1,2,3,4} }it is 2-colorable and remains 2-colorable upon removing any number of vertices from it.