Balanced hypergraph

In graph theory, a balanced hypergraph is a hypergraph that has several properties analogous to that of a bipartite graph. Balanced hypergraphs were introduced by Berge as a natural generalization of bipartite graphs. He provided two equivalent definitions. A hypergraph H = (V, E) is called 2-colorable if its vertices 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. A hypergraph in which some hyperedges are singletons (contain only one vertex) is obviously not 2-colorable; to avoid such trivial obstacles to 2-colorability, it is common to consider hypergraphs that are essentially 2-colorable, i.e., they become 2-colorable upon deleting all their singleton hyperedges. A hypergraph is called balanced if it is essentially 2-colorable, and remains essentially 2-colorable upon deleting any number of vertices. Formally, for each subset U of V, define the restriction of H to U as the hypergraph HU = (U, EU) where . Then H is called balanced iff HU is essentially 2-colorable for every subset U of V. Note that a simple graph is bipartite iff it is 2-colorable iff it is balanced. A cycle (or a circuit) in a hypergraph is a cyclic alternating sequence of distinct vertices and hyperedges: (v1, e1, v2, e2, ..., vk, ek, vk+1=v1), where every vertex vi is contained in both ei−1 and ei. The number k is called the length of the cycle. A hypergraph is balanced iff every odd-length cycle C in H has an edge containing at least three vertices of C. Note that in a simple graph all edges contain only two vertices. Hence, a simple graph is balanced iff it contains no odd-length cycles at all, which holds iff it is bipartite. Berge proved that the two definitions are equivalent; a proof is also available here. Some theorems on bipartite graphs have been generalized to balanced hypergraphs.