Balanced hypergraph

Balanced hypergraphs were introduced by Berge[1] as a natural generalization of bipartite graphs.

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.

Formally, for each subset U of V, define the restriction of H to U as the hypergraph HU = (U, EU) where

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.

A hypergraph is balanced iff every odd-length cycle C in H has an edge containing at least three vertices of C.[3] Note that in a simple graph all edges contain only two vertices.

[2]: 468–469 Some theorems on bipartite graphs have been generalized to balanced hypergraphs.

Another way to see that it is not balanced is that It contains the odd-length cycle C = (1 - {1,3,5} - 5 - {2,4,5} - 4 - {1,4,6} - 1), and no edge of C contains all three vertices 1,4,5 of C. A hypergraph is called totally balanced if every cycle C in H of length at least 3 (not necessarily odd-length) has an edge containing at least three vertices of C.[8] A hypergraph H is totally balanced iff every subhypergraph of H is a tree-hypergraph.

The Kőnig-Egervary theorem says that all bipartite graphs have the Konig property.

The initial graph is 2-colorable , as the vertices can be colored such that each edge has one of each color.

Any number of any vertices (here, 1 vertex, vertex "v2") can be deleted from the initial graph, as shown in the next graph. After re-coloring the vertices, it is shown the graph is still 2-colorable.

Any singletons , or edges with only 1 vertex, are disregarded, as these obviously cannot be 2-colored.