Buenas tardes, escribo por aquí los ejercicios en los que me tranqué del Práctico 9 - Grafos y árboles:

• Ejercicio 8. Pruebe 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.
  Supongo que se podría comenzar demostrando por el absurdo, asumiendo que no comparten vértice. Luego de elegir un camino mínimo entre ellos, usar que por ser recorrido simple, no debe de repetir vértices ni aristas. Y allí se de la contradicción, por haber asumido que no compartían vértice. No estoy segura, pero quizás también habría que probar la unicidad de dicho vértice.
  En conclusión, no estoy segura de cómo desarrollar las ideas.

• Ejercicio 7 parte f) Determine cuántos k-ciclos tiene W_n.
  Aquí los incisos anteriores me quedaron:
  a) 2n
  b) W₃ tiene 4 3-ciclos y W₄ tiene 4 3-ciclos
  c) W₃ tiene 3 4-ciclos, W₄ tiene 5 4-ciclos y W₅ tiene 5 4-ciclos
  d) W₃ y W₄ no tienen 5-ciclos y W₅ tiene 6 5-ciclos
  e) Ninguno tiene 6-ciclos
  Por lo que observo, dado n tengo el grafo W_n tal que: si k<n W_n tiene n k-ciclos. Pero si k=n W_n tiene n+1 k-ciclos. Y, k no debe de ser mayor que n, sino no tiene dicho k-ciclo. ¿Es esto cierto?. Lo que me sucedería es que no llego a concretar una respuesta cerrada para dicho inciso.