Hay una prueba proporcionada en el libro de harary pero por favor ayúdame a escribir mi propia prueba.
Prueba: (=>)Supongamos que hay al menos un ciclo impar, Partiendo el conjunto de vértices V en dos conjuntos distintos, podemos dejar que V1 sea el conjunto de vértices {v1,v3,v5,...} y V2: {v2,v4,v6,...}. Sea C* un ciclo impar arbitrario. Como es un ciclo impar entonces el recorrido en ese ciclo sería v1v2v3...v(2n+1)v1 s.t. n es un número entero. Por tanto, como v1 y v(2n+1) pertenecen a la misma partición, el grafo que contiene el ciclo no es bipartito.
(<=)A la inversa, supongamos que los ciclos son todos pares. Como la longitud de cualquier ciclo en el grafo es par, significa que hay un número par de aristas y vértices para cada ciclo, entonces podemos crear un ciclo tal que las aristas se denoten como v1v2, v2v3, v3v4,...,v(2n)v1. Al dividir cualquier ciclo par dentro del grafo por sus subíndices de tal manera que todos los vértices con subíndices pares estén separados del vértice con subíndices Impares, hemos creado un grafo bipartito.
qed
por favor, señale los errores en la prueba. ¡gracias!
