[juanNitram]

Buenas tengo problemas en demostrar la siguiente proposición:

Prueba que si \( P \) y \( Q \) son dos recorridos simples de longitud la mayor posible, en un grafo conexo, entonces tienen un vértice en común.

Me estoy planteando que \( P \) lo puedo tomar como \( x=v_1e_1v_2e_2......e_(n-1)v_n=y \) y de la misma forma \( Q \), no sé cómo seguir, agradezco ayuda!

[Luis Fuentes]

Hola

Buenas tengo problemas en demostrar la siguiente proposición:

Prueba que si \( P \) y \( Q \) son dos recorridos simples de longitud la mayor posible, en un grafo conexo, entonces tienen un vértice en común.

Me estoy planteando que \( P \) lo puedo tomar como \( x=v_1e_1v_2e_2......e_(n-1)v_n=y \) y de la misma forma \( Q \), no sé cómo seguir, agradezco ayuda!

Simplemente considera un vértice extremo de uno de los caminos; como el grafo es conexo, si los caminos no tienen vértices comunes tal vértice extremos debe de poder unirse por un camino a uno de los vértices del otro recorrido simple; por tanto tendrás un recorrido de mayor longitud, contradiciendo el hecho de que sean recorridos simples de la mayor longitud posible.

Saludos.