Graph Data Structure Question:

PROBLEM 5 (10 points): A Directed-Acyclic Graph (DAG) is exactly what the name suggests: a directed graph with no cycles. Vocab -Indegree/Outdegree: For a directed graph G (V, E), let outdegree (u) represent the out-degree of vertex u E V-Le, the number edges for which u is the source vertex (number of "outgoing arrows"). Similarly, let indegree (u) represent the in-degree of vertex uEV e., the number of edges for which u is the destination vertex (number of "incoming arrows") The following statements are true: "In any DAG (technically, with at least one vertex), there is at least one vertex u such that outdegree (u)-o" (sometimes we refer to such vertices as 'outputs" or "sinks" of the DAG). "In any DAG (technically, with at least one vertex), there is at least one vertex u such that indegree (u)-o" (sometimes we refer to such vertices as "inputs" or '"sources" of the DAG). Equivalently, "If a non-empty directed graph G is a DAG, then it has at least one sink vertex and at least one source vertex." So far so good. But how about the converse "If a given non-empty directed graph has at least one sink vertex and at least one source vertex, then it must be a DAG This turns out to be false! Your Job: Construct a counter-example (i.e., a directed-graph) demonstrating that this statement is false