Reachability in an undirected graph

Task number: 3396

Consider an undirected graph \(G\) and a relation \(R\) on its vertices such that \(xRy\) exactly when there is a path leading from \(x\) to \(y\).

  • Variant

    Show that \(R\) is an equivalence relation.

  • Variant

    What are the equivalence classes of this equivalence relation?

  • Variant

    How would this relation change if instead of the existence of a path we used the existence of a walk?

Difficulty level: Easy task (using definitions and simple reasoning)
Proving or derivation task
Cs translation
Send comment on task by email