Graph Theory Proofs (Don't understand the Concept). I just read the concept of Directed Acyclic Graphs (DAG) and I'm having some problems in solving it's proofs. I can't understand how would I prove that a DAG has a source and sink vertex. And then how would one find the source. (For examples I want to run Topological Sorting on the source - how would I find the source. - I know how topological sorting works.)
For the second part I know the source is the node whose in-degree is 0 but I don't know how will I find it.
For the first part I thought I could show that as it has no cycles then there must be at least two nodes (One whose out-degree is 0 and one whose in-degree is 0.)
 A: Let $v_0$ be any vertex of the directed acyclic graph. If $v_0$ has no incoming edges, then it is a source and we are done. Otherwise there exists $v_1$ such that $v_1\to v_0$. Again, either $v_1$ is a source or there is $v_2$ such that $v_2\to v_1\to v_0$. Apply this argument $n$ times (where $n$ is the number of nodes in the graph). Either at some point one finds a source, or we build a sequence of vertices such that $v_n\to v_{n-1}\to\dots\to v_2\to v_1\to v_0$. Note that there are $n+1$ nodes in this sequence, so there must be distinct $i,j$ such that $v_i=v_j$! Without loss of generality, we may suppose that $i<j$. Then $v_j\to v_{j-1}\to\dots\to v_i$ is a directed cycle, a contradiction to the hypothesis that the input graph does not have cycles. This means that some vertex in $\{v_{n-1},\dots,v_1,v_0\}$ is actually a source.
The very same argument can be used to prove that there is a sink in every digraph. Note that  this proof is algorithmic, in the sense that it describes a procedure that finds a source and a sink in linear time in the size of the graph.
A: Suppose, for contradiction, there are no sinks.  Pick a vertex $v_0$.  Since $v_0$ is not a sink, it has an outward pointing edge.  Let $v_1$ be the other end of an outward pointing edge from $v_0$.  Since $v_1$ is not a sink, it has an outward pointing edge.  This process can be continued indefinitely, resulting in a sequence $v_0$, $v_1$, $v_2$, $\cdots$.  Since there are only finitely many vertices, there must be a repeat somewhere.  Therefore, there is a cycle in the graph contradicting the assumption that the graph is acyclic.
The other direction is similar.
