Acyclic graph - source node

Question

How can I prove that a directed acyclic graph has a source node? A node 'a' is called source node if doesn't exists edges like ('b','a').

Answer 1

I assume you mean a directed acyclic graph?

Suppose that every vertex $v\in V$ (our vertex set) has in-degree at least $1$. Pick any starting vertex $v_0$.

Since $v_0$ has in-degree at least $1$, there is some $v_1$ so that $v_1\rightarrow v_0$ is an arc in the digraph.

Since $v_1$ has positive in-degree, there is a $v_2$ such that $v_2\rightarrow v_1$ is an arc in the digraph. Further, it cannot be the case that $v_2=\in\{v_0,v_1\}$, as otherwise it forms a cycle.

Continuing on in this way, we could continue finding new vertices $v_n$, so that $v_n\rightarrow v_{n-1}$ is an arc in the digraph for each $n$ and all of the $v_n$ are distinct.

But there's a problem here: there are only finitely many vertices in the graph! So, we can't keep generating such a sequence forever. This gives us a contradiction to our original assumption -- that is, that there is no source vertex.

Answer 2

Assume otherwise. Pick a node $a_0$. Since $a_0$ is not a source node, there exists a node $a_1$ such that there is an edge $a_1\to a_0$. Since $a_1$ is not a source node, there exists a node $a_2$ such that there is an edge $a_2\to a_1$. By induction we find an arbitrarily long chain $$ a_n\to a_{n-1}\to a_{n-2}\to\ldots \to a_2\to a_1\to a_0.$$ By the pigeon hole principle, for $n$ sufficiently large we must have $a_i=a_j$ for some $i\ne j$, that is: a cycle.

Answer 3

Pick a longest directed path. Then the starting point vertex is a source and the ending vertex is a sink.