A digraph G

is said to be monopathic if for every pair of its distinct vertices u

and v

there is at most one simple path directed from u

to v

$($and at most one from v

to u

$).$

Now let G

be an arbitrary strongly connected digraph. How many of the following five statements are true?

G

is monopathic if and only if GT

is monopathic.

G

is monopathic if and only if both DFS$($G$)$

and DFS$($GT$)$

have no forward$-$edges and no cross$-$edges.

G

is monopathic if and only if any pair of distinct simple cycles in G

have at most one vertex in common.

G

is monopathic if and only if removal of any single non$-$self$-$loop edge from G

will make it not strongly connected.

G

is monopathic if and only if DFS$($G$)$

has no forward$-$edges and no cross$-$edges, and for each vertex u

other than the DFS$-$root, there is a unique back$-$edge $($x$,$y$)$

such that x

is a descendant of u

and y

is a proper ancestor of u

$($with respect to the DFS$-$tree$).$

Question $24$Answer

a$.$

$2.$

b$.$

$5.$

c$.$

$0.$

d$.$

$3.$

e$.$

$1.$

f$.$

$4.$