Udowodnić, że w grafie spójnym każde dwie najdłuższe drogi proste mają wspólny w Cruseeer: Udowodnić, że w grafie spójnym każde dwie najdłuższe drogi proste mają wspólny wierzchołek. Wie ktoś może jak zrobić taki dowód? Studia − matematyka dyskretna

kerajs: Długość drogi w gafie to liczba różnych wierzchołków przez które przechodzi (+1 dla cyklu). Zakładam że dwie najdłuższe drogi nie mają wspólnego wierzchołka. Ponieważ graf jest spójny, to istnieje ścieżka pomiędzy pewnym wierzchołkiem z pierwszej drogi i pewnym wierzchołkiem drugiej drogi. Wierzchołki te dzielą swoje drogi na dwie części. Biorąc po dłuższej części każdej z tych dróg i wspomnianą wcześniej ścieżkę otrzymuję nową drogę która jest dłuższa od co najmniej jednej z pierwotnych najdłuższych dróg. Ergo, nie można tak wybrać dwóch najdłuższych dróg aby były rozłączne.

Cruseeer: Czyli końcowo nie da się tego udowodnić, gdyż jest to nie prawda?

I'm back: Przeczytaj ponownie co Kerajs napisał. Tym razem ze zrozumieniem