Def. (Grafo Bipartita)
Un grafo bipartita es el cuyos vertices pueden ser particionados en dos subconjuntos
y , tales que cada arista tiene un extremo en cada uno; esa partición es llamada bipartición del grafo. Un grafo bipartita completo es un grafo bipartita simple con la bipartición
, el cual cada vértice de está unido con cada vértice de ; si y , tal grafo se denota .
Ejemplo.
es bipartita , y es bipartita completo
