Un grafo bipartito es un Grafo donde el conjunto de vértices se puede dividir en dos conjuntos disjuntos y de tal manera que cada arista en conecta un vértice en con un vértice en de modo que no existen aristas que conecten vértices dentro del mismo conjunto o . Formalmente, para toda arista , se cumple que si entonces .
En particular, los grafos bipartitos son bicoloreables.
Se verifica que un grafo es bipartito si y solo si no tiene ciclos de longitud impar. MISSING-PROOF