Suponga que este grafo es bipartito. Entonces el conjunto de vértices puede ser particionado en dos subconjuntos mutuamente disjuntos, tales que lo...

Suponga que este grafo es bipartito. Entonces el conjunto de vértices puede ser particionado en dos subconjuntos mutuamente disjuntos, tales que los vértices en cada subconjunto estén conectados por extremos solamente a vértices en el otro subconjunto y no a vértices en el mismo subconjunto. Ahora 1 está en un subconjunto de la partición, digamos V1. Como 1 está conectado por extremos a 2 y 3, entonces 2 y 3 deben estar en el otro subconjunto, V2. Pero 2 y 3 están conectados entre sí por un extremo. Esto contradice el hecho de que ningún vértice en V2 está conectado por extremos a otros vértices en V2. Así que la suposición es falsa y entonces el grafo no es bipartito.