Ungerichteter Graph/Verbunden/Äquivalenzrelation/Fakt/Beweis

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