Vertices equivalence relations

Problem 1. Let G~ be an arbitrary digraph.
(a) We define a relation ⇠ on the set V (G~ ) of vertices of G~ as
follows: for any u, v 2 V (G~ ) let u ⇠ v hold if and only if u = v
or G~ has a directed (u, v)-walk as well as a directed (v, u)-walk.
Show that
(i) ⇠ is an equivalence relation, and
(ii) for each equivalence class C of ⇠, the induced subgraph
C~ of G~ with vertex set C is strongly connected.
Definition. The induced subgraphs C~ of G~ described in (ii)
above are called the strongly connected components of G~ .
(b) Let S denote the set of strongly connected components of G~ , and define a relation
 on S as follows: for any C, ~ D~ 2 S, let C~  D~ if and only if C~ = D~ or for some
vertices c in C~ and d in D~ there exists a directed (c, d)-walk in G~ . Show that
(i)  is a partial order on S.
(ii) Consequently, for any distinct strongly connected components C~ and D~ of G~ ,
all edges of G~ between vertices in C~ and vertices D~ point in the same direction.
1
MT D r r
I
µ
E i p