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 . Como X e Y no están vacíos, G tiene al menos dos vértices. Si C es cualquier circuito en G, sea

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 = G. Tome v0ÎV y establezca

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.