Todo grafo bipartito tiene ciclos de longitud par

Un grafo $G$ es bipartito si y sólo si no tiene ciclos de longitud impar.

Demostración:

Un grafo $G = (V, X)$ es bipartito $⟺$ cada una de sus componentes conexas es bipartita

Un grafo $G = (V, X)$ no tiene ciclos impares $⟺$ cada una de sus componentes conexas no tiene ciclos impares

Alcanza con demostrar el teorema para grafos conexos. Entonces vamos a suponer que $G$ es conexo.

$\Rightarrow$ $G$ bipartito, $V = (V_{1}, V_{2})$ bipartición.

Si $G$ no tiene ciclos, listo, porque se cumple que $G$ no tiene ciclos de longitud impar.

Supongamos entonces que $G$ tiene algún ciclo y sea $C = v_{1} v_{2} \dots v_{k} v_{1}$ un ciclo de $G$ . Sin pérdida de generalidad, supongamos que $v_{1} \in V_{1}$ . Como $(v 1, v 2) \in X$ , entonces $v_{2} \in V_{2}$ . En general, $v_{2 i + 1} \in V_{1}$ y $v_{2 i} \in V_{2}$ . Como $v_{1} \in V_{1}$ y $(v_{k}, v_{1}) \in X$ , debe pasar $v_{k} \in V_{2}$ . Luego $k = 2 i$ para algún $i$ , lo que implica que $l (C)$ es par.

⇐=) $G$ sin ciclos impares. Sea $u$ cualquier vértice de $V$ . Definimos:

\begin{array}{r} V_{1} = {v \in V tq d (u, v) es par} \cup {u} \\ V_{2} = {v \in V tq d (u, v) es impar} \end{array}

$V_{1}$ , $V_{2}$ definen una partición de $V$ (ya que como $G$ es conexo no hay vértices a distancia $\infty$ de $u$ ). Veamos que definen una bipartición (es decir que no existe arista entre un vértice de $V_{1}$ y uno de $V_{2}$ ).

Supongamos que no es bipartición, es decir existen $v, w \in V_{1}$ (podría ser $V_{2}$ ) tales que $(v, w) \in X$ . Si $v = u$ , entonces $d (u, w) = 1$ , pero esto no puede pasar porque $d (u, w)$ es par. Lo mismo para $w$ . Luego, $u \neq v, w$ .

Sea $P$ un camino mínimo entre $v$ y $u$ y $Q$ uno entre $v$ y $w$ . Como $u, w \in V_{1}$ , $P$ y $Q$ tienen longitud par.

Sea $z$ el vértice común a $P$ y $Q$ tal que $P_{z v}$ y $Q_{z w}$ no tienen vértices en común (solo $z$ ). Tiene que suceder que $d (u, z) = l (P_{u z}) = l (Q_{u z})$ , de lo contrario $P$ y $Q$ no serían caminos que definen las distancias respectivas. Entonces $l (P_{z v})$ y $l (Q_{z w})$ tienen igual paridad. Esto implica que el ciclo $P_{z v} (v, w) Q_{w z}$ tiene longitud impar, contradiciendo la hipótesis. Esta contradicción se generó por suponer que existe $v, w \in V_{1}$ tales que $(v, w) \in X$ .