Proof. Given a DAG $G$, for every vertex $v$ in $G$, there is a path from $v$ to some sink in $G$. Given a DAG $G$, for every vertex $v$ in $G$, there is a path from $v$ to some sink in $G$.
I am really having difficult understand the given solution since I am still improving my English skill. Thank you for any tips to understand it.
Given solution:
True. Consider the proof below.
Proof. Suppose by contradiction that there exists a vertex $v_0$ such that there is no path from $v_0$ to a sink. Suppose that $G$ has $n$ vertices. Then we can make a path by following any of the outgoing edges of $v_0$. Call the next vertex in the path $v_1$. Since $v_1$ is not a sink (How do we know V1 is not a sink?), it has an outgoing edge (Yes, we call a vertex a sink when it has not outgoing edges, but how do we know it has outgoing edge at the first place?), follow one of its outgoing edge and call the adjacent vertex $v_2$. Keep on doing this until you get a list of $n+1$ vertices $v_0,v_1,\ldots,v_n$. (Even we finish all the vertex, how do we know there are at least two vertices in the list are the same? I don't think it is not necessary; for example: $A\to B\to C\to D$, it is DAG and even we visited all the vertices start from $0$ to $n+1$ there doesn't exit a cycle.) By the pigeonhole principle, at least two vertices in this list are the same and therefore there exists a cycle.
Thank you again.
 A: Proof. Suppose by contradiction that there exists a vertex V0 such that there is no path from V0 to a sink. Suppose that G has n vertices. Then we can make a path by following any of the outgoing edges of V0. Call the next vertex in the path V1. Since v1 is not a sink(How do we know V1 is not a sink? ),
Because it was assumed there is no path from v0 to a sink.
it has an outgoing edge(Yes. we call a vertex a sink when it has not outgoing edges, but how do we know it has outgoing edge at the first place?),
Each vertex in the list has an out going edge because it cannot be a sink.
follow one of its outgoing edge and call the adjacent vertex v2. Keep on doing this until you get a list of n + 1 vertices V0, V1, .... Vn.(even we finish all the vertex, How do we know there are at least two vertices in the list are the same?,
Because picking n + 1 vertices out of n, one has to be picked twice.
I don't think it is not necessary; for example: A->B->C->D. it is DAG and even we visited all the vertices start from o to n+1. there doesn't exit a cycle. )
That example violates the assumption that there is a vertex with no path to a sink.
By the pigeonhole principle, at least two vertices in this list are the same and therefore there exists a cycle.
Correct.
