A digraph \(D(V,E,\alpha,\omega)\) or an undirected graph \(G(V,E,\gamma)\) is called bipartite, if its vertices can be split into two subsets \(A\) and \(B\) in such a way that each edge of the graph joins a vertex in \(A\) and a vertex in \(B\). Formally, if there is a partition of vertices \(V=A\cup B,~ A\cap B=\emptyset\) with
In particular, a bipartite graph has no loops.
The following figure shows a bipartite digraph. The vertices of one partition \(A\) are colored blue, while the vertices of the other partition \(B\) are colored orange. Please note that there are only edges between vertices with alternating colors. In particular, there are no loops:
Theorems: 3 4