Para probar la afirmación anterior, resolvemos los siguientes problemas.
Comenzando en cualquier vértice en cualquier componente de , asigne el color rojo a y proceda a colorear vértices a lo largo de caminos simples desde , alternando entre rojo y azul. De esa manera, cada vértice en el componente finalmente se alcanza y se colorea.
En el procedimiento descrito anteriormente, el color asignado a un vértice depende de la longitud del camino seguido desde a . Un vértice alcanzado por un camino de longitud impar se colorea de azul, mientras que un vértice alcanzado por un camino de longitud par se colorea de rojo.
(a) Dejar ser vértices en un gráfico que no contiene ciclos impares y suponga que hay dos caminos desde a , uno de longitud impar y otro de longitud par. Muestre que esta situación es imposible derivando una contradicción.
(b) Demuestre que si cada componente de un gráfico es bipartito, entonces el gráfico completo es bipartito. Luego muestre que con los vértices de algún componente coloreado como se describe arriba, ningún borde tiene el mismo color asignado a sus dos extremos.
Mi pregunta es ¿qué estamos demostrando al resolver el problema (a)? ¿Estamos demostrando que no hay dos aristas que compartan los mismos extremos?
En la parte a) estamos demostrando que un vértice nunca se coloreará tanto de azul como de rojo. Esto es útil porque nos dice que, en cada componente conexa de , a cada vértice se le asignará exactamente un color y, por construcción, sus vecinos siempre tendrán el color "opuesto". Entonces, los vértices azules y los vértices rojos en cualquier componente dado forman las dos "partes" de la bipartición de este componente. Entonces, por la parte b), podemos "reunir" los vértices rojos y los vértices azules en cada componente para formar la bipartición de .
mdave16
usuario84413
bof