[Math] Prove that a directed graph with no cycles has at least one node of indegree zero

graph theory

How would I show this? I know a directed graph with no cycles has at least one node of outdegree zero (because a graph where every node has outdegree one contains a cycle), but do not know where to go from here.

Best Answer

Suppose that there exists a graph with no cycles and there are no nodes of indegree $0$. Then each node has indegree $1$ or higher. Pick any node, since its indegree is $1$ or higher we can go to its parent node. This node has also indegree $1$ or higher and so we can keep doing this procedure until we arrive at the node we already visited. This will prove that there exists a cycle which contradicts our initial assumption. So we proved that every directed graph with no cycles has at least one node of indegree zero.