Relacja równoważności na zbiorze wierzchołków grafu

[Majeskas]

Należy wykazać, że relacja na zbiorze wierzchołków grafu, taka że \(\displaystyle{ v}\) jest w relacji z \(\displaystyle{ u}\), jeśli łączy je ścieżka, jest relacją równoważności. Mam problem ze zwrotnością. Definicje ścieżek, jakie znalazłem, nakazują, by wierzchołki łączyła krawędź, podczas gdy wierzchołek nie musi być połączony krawędzią z sobą samym. Nie wiem, jak wybrnąć z tego formalnego kłopotu.

[Gouranga]

Przy zwrotności masz ścieżkę złożoną z tego wierzchołka, jej początek i koniec jest tym wierzchołkiem więc można to traktować jako ścieżkę. Dwóch wierzchołków nie łączy ścieżka, jeśli znajdują się w dwóch różnych składowych spójności grafu, a jeden wierzchołek nie może należeć jednocześnie do dwóch różnych składowych więc musi być sam ze sobą w ścieżce.