Question 1: Yes. If we are popping v off the stack, then each of v's children is either: currently on the stack (which can't be the case since the graph is acyclic, and the child being on the stack implies a cycle between the child and v), or is finished being explored (which can't be the case here since v is the first vertex to be finished). Thus, v must not have any children, and thus must be a sink vertex. Alternatively: as the book explains, in a DAG, the vertex with the smallest post number is always a sink. Question 2. No. pre(u) < pre(v) means u is visited first, but a depth-first search will finish executing v before it finishes u. Or: No. DFS uses a stack, so if u is pushed on the stack before v, then v must be popped off before u can be popped off. Or: No. See the end of Section 3.2.4 in the book.