Efectivamente, la idea que propones no funciona, pero la conectividad es el menor de tus problemas. Supongamos que $G = (V,E)$ es nuestro grafo bipartito y que el conjunto de vértices $H \subseteq V$ define una trayectoria isométrica. Un vértice $v \in V \setminus H$ en el mismo componente que $H$ no necesita tener un único vértice más cercano en el camino, por lo que el mapa no está bien definido. Además, aunque $v \in V \setminus H$ tiene un único vecino $w$ en $H$ entonces la cartografía $v$ a $w$ es una mala idea, ya que nunca puede ser un homomorfismo (hay una arista $vw$ en $G$ pero no hay ningún borde desde $w$ a $w$ ).
Esto nos lleva a una propiedad fundamental (y algo confusa) de los homomorfismos de grafos (suponiendo que sólo consideremos grafos sin bucles): ¡no se pueden enviar extremos diferentes de una arista al mismo vértice! En otras palabras, la preimagen de cada vértice debe ser un conjunto independiente. Esto da lugar a la siguiente caracterización interesante del número cromático de un grafo: es el número mínimo $\ell \in \mathbb{N}$ de modo que existe un homomorfismo $G \to K_\ell$ .
En particular, cualquier grafo bipartito $G = (V,E)$ tiene un homomorfismo hacia $K_2$ . Si dejamos que $A,B \subseteq V$ denotan las clases de color de $G$ entonces los vértices de $A$ se envían a un vértice y los vértices en $B$ a la otra.
![bipartite graph homomorphism]()
Por lo tanto, sólo tenemos que preocuparnos realmente del componente que contiene $H$ los demás componentes pueden asignarse a una arista arbitraria en $H$ . Por lo tanto, podemos suponer sin pérdida de generalidad que $G$ está conectado. Sea $v_0 \in H$ sea uno de los puntos finales de nuestra trayectoria isométrica, y sea $k := \epsilon(v_0)$ denotan su excentricidad (es decir, la distancia máxima desde $v_0$ a cualquier otro vértice). Sea $P_{k+1}$ denota el grafo de caminos en $k + 1$ vértices $x_0,\ldots,x_k$ . Definimos un homomorfismo $f : G \to P_{k+1}$ de la siguiente manera: $$ f(w) = x_{d(v_0,w)}. $$ En otras palabras: $v_0$ se envía a $x_0$ todos los vecinos de $v_0$ se envían a $x_1$ los vecinos de los vecinos de $v_0$ se envían a $x_2$ etc. No es demasiado difícil demostrar que se trata de un homomorfismo; lo dejaré como ejercicio. (Supongamos que $u,w\in V$ son adyacentes, entonces es fácil ver que $u$ y $w$ se envían a vértices vecinos o al mismo vértice. Para descartar esto último, utilice que $G$ es bipartita).
Ahora dejemos que $\ell := |H|$ denotan el número de vértices de nuestra trayectoria isométrica. Obsérvese que tenemos $\ell \leq k + 1$ . Elegimos algún homomorfismo $h : P_{k+1} \to P_\ell$ tal que el primer $\ell$ vértices de $P_{k+1}$ se asignan al primer $\ell$ vértices de $P_\ell$ . Por ejemplo, $g$ podría ser el siguiente homomorfismo en zigzag (ilustrado aquí para el caso $k = 27$ y $\ell = 7$ ):
![zigzag homomorphism]()
Por último $h : P_\ell \to H$ sea el homomorfismo que identifica $P_\ell$ con nuestra ruta original $H$ de tal forma que el primer vértice de $P_\ell$ se envía a $v_0$ . Consideremos ahora la composición $$ G \stackrel{f}{\longrightarrow} P_{k+1} \stackrel{g}{\longrightarrow} P_\ell \stackrel{h}{\longrightarrow} H. $$ Esto da un homomorfismo $\varphi : G \to H$ . No es tan difícil ver que $\varphi$ es una retracción, de modo que $H$ un retracto.
Por último, como nota al margen, me gustaría señalar que un camino que se no isométrico no puede ser un repliegue: ahora hay algún camino más corto $H'$ entre los extremos de $H$ pero no existe un homomorfismo $H' \to H$ que preserva ambos puntos finales. Además, si $G$ no es bipartito, entonces ningún camino en $G$ puede ser un repliegue; de lo contrario tendríamos una 2-coloración de $G$ dada por la composición $G \longrightarrow P_m \longrightarrow K_2$ de homomorfismos de grafos. (En términos más sencillos: un 2-coloreado del camino se puede elevar a lo largo de la retracción para dar un 2-coloreado de $G$ .) Por lo tanto, hemos demostrado la siguiente caracterización:
Proposición. Sea $G$ sea un grafo y $P$ sea un camino en $G$ con al menos $2$ vértices. Entonces $P$ es un repliegue si y sólo si $G$ es bipartita y $P$ es isométrico.
(Un vértice sólo es un repliegue si $G$ no tiene aristas).
