directed graph is said to be semi$-$connected if for all pairs of vertices u and v$,$ we have u$$v$,$

or v$$u$,$ or both.

$($The notation u$$v means u can reach v by a directed path.$)$

$($a$)$ Suppose G is a directed acyclic graph with n vertices, and suppose we have performed a

topological sort on G$.$ Let vi denote the ith vertex in the topological sort order.

Show that G is semi$-$connected if and only if there is an edge $($vi$,$ vi$+1)$ for all i $=1,2,...,$ n$-1.$

$(50\%$ of the whole point$)$