Ungerichteter Graph/Verbunden/Äquivalenzrelation/Fakt/Beweis

Beweis

Jeder Knotenpunkt ist durch den leeren Kantenzug mit sich selbst verbunden. Dies sichert die Reflexivität. Wenn ${}u$ und ${}v$ durch den Kantenzug ${}u=v_{1},v_{2},\ldots ,v_{r-1},v_{r}=v$ miteinander verbunden sind, so ist ${}v$ mit ${}u$ durch den umorientierten Kantenzug ${}v_{r},v_{r-1},\ldots ,v_{2},v_{1}$ verbunden. Dies sichert die Symmetrie. Wenn ${}u$ mit ${}v$ durch den Kantenzug ${}u=v_{1},v_{2},\ldots ,v_{r}=v$ verbunden ist und ${}v$ mit ${}w$ durch den Kantenzug ${}v=w_{1},w_{2},\ldots ,w_{s}=w$ verbunden ist, so ist ${}v$ mit ${}w$ durch den zusammengesetzten Kantenzug ${}u=v_{1},v_{2},\ldots ,v_{r}=v=w_{1},w_{2},\ldots ,w_{s}=w$ verbunden. Dies sichert die Transitivität.

Zur bewiesenen Aussage