1. For each statement below, decide whether it is TRUE or FALSE and circle the right one. In each case attach a very brief explanation of your answer. (a) 0)) Let G be a DAG with n 3_> 2 vertices and let the sequence or he a topological sort of G. If 11. appears before 1'; in a then there exists a directed path from a to t: in G. Solution: False Counter example: 9 A topological sort would be 1423. Let 1:. = 1 and v = 4. However, there is no path from 1 to 4. A strongly connected digraph with at least two nodes can have neither sources nor sinks. Solution: True. A strongly connected digraph with at least two nodes can have neither sources nor sinks. Assume for contradiction that there is source '0. Then there must he no edges leading to w, and therefore no paths to v. The graph cannot be stroneg connected, so we have a contradiction. By similar logic, there cannot be any sinks