Gráfica (o grafo) bipartita

Una gráfica $G$ es bipartita si existe una partición de los vértices de $G$ en dos conjuntos $V_1$ y $V_2$ (no vacios) de forma que cada arista de $G$ tenga un extremo en $V_1$ y el otro en $V_2$

Por ejemplo, la gráfica de la siguiente figura es bipartita:

Los véritces rojos forman el conjunto $V_1$ y los vértices verdes el conjunto de vértices $V_2$.