Q1: 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.

Q2: We are given a DFS tree. Direct the tree edges away from the root. Show that each vertex has a directed path to the root that uses at most one backward edge, if and only if all the leaves have an edge to the root.