En un grafo conexo, si el camino máximo que se puede hacer es de longitud 100, y hay dos caminos de longitud 100, ¿no son el mismo camino?

Question

He aquí la cuestión:

Sea G un grafo conexo. (Recordemos que esto significa que cada dos vértices de G pueden estar unidos por un camino que empieza en uno y termina en el otro).

Supongamos también que G tiene la siguiente propiedad: no hay ningún camino de longitud superior a 100 en G. (Recordemos también que la longitud del camino es el número de aristas que atraviesa, que es uno menos que el número de vértices en el camino).

Demostrar que si P1 y P2 son dos caminos en G con longitud exactamente 100, entonces debe haber algún vértice que pertenezca tanto a P1 como a P2.

¿No están todos los vértices conectados en un grafo conectado? (es decir, el camino más largo tocará todos los vértices) En cuyo caso la longitud máxima del camino sería el número de vértices menos 1. ¿No significaría eso que P1 y P2 comparten un vértice porque comparten todos los vértices?

Si me equivoco supongo que mi pregunta sería "¿Cuál es el ejemplo de un grafo con una longitud de camino máxima en el que dos caminos que son iguales a la longitud de camino máxima sólo comparten un vértice?"

Answer 1

Toma un camino $P_1$ de longitud $100$ tiene $101$ vértices. Sea $v$ sea el vértice central, y únale otros dos caminos disjuntos de longitud $50$ cada uno. Ahora tienes una gran X en la que cada uno de los cuatro brazos es un camino de longitud $50$ . Este gráfico tiene $\binom42=6$ trayectorias de longitud $100$ y ningún camino más, y siempre que se elija uno de los tres pares de caminos maximales que comparten sólo el vértice $v$ se tienen dos caminos de longitud $100$ con un único vértice en común.

Añadido: Para obtener el resultado real, supongamos que $P_1$ y $P_2$ no tienen ningún vértice en común. Sea $Q$ sea el camino más corto entre algún vértice de $P_1$ a algún vértice de $P_2$ ; obsérvese que los extremos de $Q$ son los únicos vértices que comparte con $P_1\cup P_2$ . Demuestre que si $u$ es el punto final de $Q$ en $P_1$ y $v$ es el punto final de $Q$ en $P_2$ entonces hay un punto final $x$ de $P_1$ y un punto final $y$ de $P_2$ tal que el camino desde $x$ a $u$ a lo largo de $P_1$ de $u$ a $v$ a lo largo de $Q$ y de $v$ a $y$ a lo largo de $P_2$ tiene una longitud superior a $100$ .