Si un grafo no tiene ciclos de longitud impar, entonces es bipartito: ¿es correcta mi demostración?

Question

Se me ocurrió una prueba de

Gráfico $G$ no tiene ciclos de longitud impar $\implies$ $G$ es bipartita.

así:

Sin pérdida de generalidad, consideremos sólo un componente conectado porque si cada componente conectado de un grafo es bipartito, entonces todo el grafo es bipartito.

Recoger un vértice al azar $v$ en $G$ calcula la longitud del camino simple más corto desde $v$ a cualquier otro nodo, llame a este valor distancia de $v$ y dividir los nodos en 2 grupos según la paridad de su distancia a $v$ . Si podemos demostrar que los nodos que pertenecen al mismo grupo no pueden ser adyacentes, entonces sabemos que realmente obtenemos una partición del $G$ que cumplen la definición de grafo bipartito.

Ahora, para introducir una contradicción, supongamos dos nodos $x, y$ con una distancia par o impar de $v$ son adyacentes, entonces el camino simple más corto $\langle v, x \rangle$ , $\langle v, y \rangle$ y el borde $\{x, y\}$ contiene un ciclo con longitud impar, lo que es contradictorio con que $G$ no tiene ciclos de longitud impar. En otras palabras, los nodos con distancia par o impar de $v$ no pueden ser adyacentes, que es exactamente lo que necesitamos.

Así que mi pregunta es, ¿es correcta mi prueba? ¿Y hay algún método más sencillo para demostrar la proposición?

Editar:

(para responder al comentario de Srivatsan Narayanan)

Para demostrar que $\langle v, x \rangle$ y $\langle v, y \rangle$ junto con $\langle x, y \rangle$ contiene un ciclo con longitud impar es evidente cuando $\langle v, x \rangle$ y $\langle v, y\rangle$ son disjuntos. Cuando no es el caso, demos el último nodo compartido por $\langle v, x\rangle$ y $\langle v, y\rangle$ el nombre $v'$ . Así que los tres nodos $v', x, y$ forma un ciclo con longitud $\newcommand{\len}{\operatorname{len}}$

$$ L = \len(\langle v', x \rangle) + \len(\langle v', y \rangle) + 1 = \len(\langle v, x \rangle) + \len( \langle v, y \rangle) - 2 \cdot \len(\langle v, v'\rangle) + 1 .$$

donde $\len()$ significa la longitud del camino más corto.

Como $\len(\langle v, x \rangle)$ y $\len(\langle v , y \rangle)$ son ambos pares o Impares, entonces $L$ debe ser impar. Por lo tanto, en ambos casos, disjuntos o no, $\langle v, x \rangle$ , $\langle v, y \rangle$ y $\langle x, y\rangle$ contiene un ciclo de longitud impar.

Edición2

Para ver $\len(\langle v, x \rangle) = \len(\langle v, v'\rangle) + \len(\langle v', x \rangle)$ podemos demostrar simplemente que ambos $\langle v, v' \rangle$ y $\langle v', x \rangle$ son ambos el camino más corto. Y eso es obvio, porque si no es así, existe un camino más corto que $\langle v, v' \rangle$ de $v$ a $v'$ o existe un camino más corto que $\langle v', x\rangle$ de $v'$ a $x$ entonces $\langle v, x \rangle$ no puede ser un camino más corto.

Answer 1

Creo que la cuestión está resuelta a satisfacción del OP. Véase los comentarios y las revisiones de la pregunta para las discusiones pertinentes. $\newcommand{\len}{\operatorname{len}}$

---

Aquí presento una prueba diferente, y -en mi opinión- conceptualmente más limpia, del mismo hecho.

Supongamos que $G$ es un grafo conexo cuyos ciclos son todos de longitud par. Generalizamos esto ligeramente a lo siguiente

Propuesta. Cualquier paseo cerrado $G$ tiene una longitud uniforme.

Prueba. Hacia una contradicción, supongamos que no. Dejemos que $W$ sea un paseo cerrado de longitud impar tal que la longitud de $W$ es lo más pequeño posible. Por hipótesis, $W$ no puede ser un ciclo; es decir, $W$ visita algún vértice intermedio al menos dos veces. Por lo tanto, podemos escribir $W$ como la "concatenación" de dos paseos cerrados no triviales $W_1$ y $W_2$ cada uno de los cuales es más corto que $W$ . Además, $\len W_1 + \len W_2 = \len W$ que es impar. Por lo tanto, al menos uno de $W_1$ y $W_2$ es de longitud impar, contradiciendo la minimidad de $W$ . Por lo tanto, no puede haber ningún paseo cerrado en $G$ de la longitud de impar. $\quad\quad \Box$

Partición del gráfico en vértices pares e Impares. Ahora, fija un vértice $v$ y definir $E$ (resp. $O$ ) es el conjunto de vértices $x$ en $G$ tal que existe un camino de longitud par (resp. de longitud impar) desde $v$ a $x$ . Los conjuntos $E$ y $O$ partición $V$ :

• Suponiendo que $G$ está conectado, entonces claramente $E \cup O = V$ .

• Ahora demostramos que $E \cap O = \emptyset$ . Por el contrario, supongamos que $x$ está en ambos $E$ y $O$ . Entonces hay un $v$ - $x$ caminar $W_1$ de longitud uniforme y otra $W_2$ de la longitud de impar. Entonces el paseo $W_1 \circ \operatorname{reverse} (W_2)$ es un paseo cerrado en $G$ de la longitud de impar, una contradicción.

Por último, demostramos que cada arista cruza el corte $(E, O)$ :

• Supongamos que $x \in E$ y $xy$ es una arista. Entonces existe un $v$ - $x$ caminar $W$ de longitud uniforme. Por lo tanto, $W \circ xy$ es un $v$ - $y$ caminar y tiene la longitud de impar. Por lo tanto, $y \in O$ .

• Del mismo modo, si $x \in O$ y $xy$ es una arista, podemos demostrar que $y$ está en $E$ . Esta prueba es similar al caso anterior.

Esto establece que $G$ es bipartita, como se desea.