Condiciones necesarias y suficientes para dos puntos
La condición necesaria y suficiente para que un grafo no dirigido G sea bipartito es que G tenga al menos dos vértices y las longitudes de todos sus bucles sean números pares.
Necesidad de prueba.
Sea G un grafo bipartito
C = (v0,v 1,v2,…,v l-1,v l = v0)
donde vi (i = 0 ,1,…,l) debe aparecer alternativamente en X e Y. Supongamos
{v0,v2,v4,…,v l = v0} Í v3,v5,…,v l-1} Í Y
Por lo tanto, l debe ser un número par, por lo que hay un número par de aristas en C.
Reconfirmar la suficiencia.
Supongamos que todos los bucles de G tienen longitudes pares y sea G un gráfico conexo (sin pérdida de generalidad, si G no es conexo, se puede hacer la siguiente discusión sobre cada rama conexa de G).
Sea V el conjunto de vértices de G y E el conjunto de aristas. Ahora construya X, Y, de modo que
X = {v | v= v0 o v a v0 con una ruta de longitud uniforme}
Y = V-X
X Obviamente No vacío. Ahora necesitamos demostrar que Y no está vacío y que ninguna arista tiene ambos extremos en X o ambos en Y.
Dado que |V|≥2 y G es un gráfico conectado, v0 debe tener vértices adyacentes, establecidos en v1, entonces v1ÎY, por lo tanto, Y no está vacío.
Supongamos que hay una arista (u, v), tal que uÎX, vÎX. Entonces, hay un camino de longitud par de v0 a u, o u = v0; hay un camino de longitud par de v0 a v, o v = v0; En cualquier caso, hay un camino cerrado de longitud impar de v0 a v0, por lo que hay un bucle de longitud impar de v0 a v0 (porque la longitud del bucle que se puede eliminar del camino cerrado es siempre un número par) , y el problema es la contradicción. Por lo tanto, no puede haber una arista (u, v) tal que tanto u como v estén en X.
La demostración de "ningún borde tiene dos puntos finales, todos en Y" se puede realizar imitando lo anterior. Se invita a los lectores a pensar en ello.