przykład grafu 3-spójnego

[forever17]

Podać przykład grafu 3-spójnego takiego, że każde dwa najdłuższe cykle mają dokładnie 3 wierzchołki wspólne.

Jedyne co mi przychodzi do głowy to trójkąt. Co sądzicie o takim rozwiązaniu?

[Ein]

Trójkąt to sensowna odpowiedź.

[forever17]

Mam dwie wątpliwości odnośnie tego rozwiązania:

1) czy punkt jest grafem spójnym?

2) czy cykl \(\displaystyle{ v_1,v_2,v_3,v_1}\) jest różny od cyklu \(\displaystyle{ v_2, v_3,v_1,v_2}\)? Czyli inaczej mówiąc - czy trójkąt ma tylko jeden cykl czy jest ich więcej?

[Ein]

1) jest, z definicji: dla każdych dwóch wierzchołków istnieje ścieżka je łącząca -- w tym przypadku po prostu nie ma dwóch wierzchołków różnych, więc kwantyfikator przebiega zbiór zawierający tylko parę składającą się z dwóch tych samych elementów

2) wiesz co? myślę, że to zależy od potrzeb, ale jednak wszelkie zdroworozsądkowe argumenty stoją za tym, aby to był jeden i ten sam cykl