Hola
Bienvenido al foro.
Recuerda leer y seguir las
reglas del mismo así como el
tutorial del LaTeX para escribir las fórmulas matemáticas correctamente
Cómo puedo demostrar que 2 trayectorias máximas dentro de un grado tamaño n, tienen al menos un vértice en común
Para que el resultado sea cierto el grafo debe de ser conexo. En ese caso si tuvieses dos trayectorias máximas de longitud \( n \) disjuntas, tendrían que poder unirse por un camino. Es decir existe un camino de longitud al menos \( 1 \) que une dos vértices \( P \) y \( Q \) en cada una de las dos trayectorias.
Ahora si a ese camino le añades las dos mitades de mayor longitud en cada trayectoria tienes un camino de longitud mayor o igual que:
\( 1+\dfrac{n}{2}+\dfrac{n}{2}=n+1 \)
Esto contradice la maximalidad de las trayectorias originales.
Saludos.
