A bipartite graph is a graph $G = (V, E)$ whose vertices can be partitioned into two sets ($V = V_1 \cup V_2$
and $V_1 \cap V_2 = \emptyset$) such that there are no edges between vertices in the same set (for instance, if
$u, v \in V_1$, then there is no edge between $u$ and $v$).
There are many other ways to formulate this property. For instance, an undirected graph
is bipartite if and only if it can be colored with just two colors. Another one: an undirected graph is
bipartite if and only if it contains no cycles of odd length.
