Question 4: Let G be a directed graph. A kernel S is a subset of V so that there are no edges between any two vertices of S, and for every v 6 S, there is an s S so that s 7 v E. 1. Show that a general directed graph may not have a kernel 2. Show that a DAG always has a unique Kernel. Hint: that vertices of indegree 0 must be in the kernel 3. Give an algorithm to find a kernel in a DAG.