Gráfica Bipartita

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

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

Los véritces rojos forman el conjunto V1 y los vértices verdes el conjunto de vértices V2