Coloración de vertices

($\Rightarrow$) Supongamos que G es bipartita con bipartición $H_1,H_2$, coloreemos cada vértice en $H_1$ de color 1 y cada vértice en $H_2$ de color 2. Como ningún par de vértices $v,u$ con $v \in H_1, u \in H_2$ son adyacentes, entonces la coloración es buena y $H_1$ y $H_2$ son las clases cromáticas para esta 2-coloración.

($\Leftarrow$) Supongamos que podemos colorear bien a G solamente con 2 colores. Sea $H_1 = \{v \in G |$ v es de color 1$\}, H_2=\{v \in G |$ v es de color 2$\}$ las clases cromáticas de G con esta coloración. Por definición ninguno de los vértices de $H_1$ es adyacente a ninguno de los de $H_2$. Además $H_1 U H_2 = V(G)$, entonces $H_1, H_2$ es una bipartición de G