Demostrar que si $P$ y $Q$ son dos caminos más largos en un grafo conexo, entonces $P$ y $Q$ tienen al menos un vértice en común.

Question

Estoy trabajando en el siguiente ejercicio de teoría de grafos:

Demostrar que si $P$ y $Q$ son dos caminos más largos en un grafo conexo, entonces $P$ y $Q$ tienen al menos un vértice en común.

A través de una forma gráfica ha sido fácil mostrar esa condición en cada gráfico, pero ¿hay alguna formalización que me ayude a mostrarlo? Gracias de antemano por cualquier ayuda o pista.

Answer 1

Digamos que tenemos dos caminos $P$ y $Q$ sin vértices en común. Como el grafo es conexo, debe haber un camino desde cualquier vértice en $P$ a cualquier vértice de $Q$ . Toma uno de esos caminos. Tome una parte $R$ de ese camino con la propiedad de que un punto final está en $P$ el otro punto final está en $ Q$ y en caso contrario no comparte ningún vértice con $P$ o $Q$ . Por nuestra suposición de que $P$ y $Q$ no tienen vértices en común, $R$ tiene una longitud mínima de $1$ .

Ahora hay cuatro caminos que van desde un punto final de $P$ , sigue $P$ hasta llegar a $R$ , entonces sigue $R$ todo el camino hasta $Q$ y luego sigue $Q$ a un punto final de $Q$ . Al menos uno de estos cuatro debe ser necesariamente más largo que ambos $P$ y $Q$ , lo que significa $P$ y $Q$ no pueden ser caminos más largos.