Prove that a directed graph with no cycles has at least one node of indegree zero 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.
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.
This proof will prove that DAGs (Directed Acyclic Graphs) have at least one node of indegree $ 0 $ and one node of outdegree $ 0 $ as well:
A DAG will contain all paths of finite length (Because of absence of cycles). Let's consider WLOG, the longest path $ P $ of the graph in consideration from a vertex $ u $ (our source) to vertex $ v $ (our destination). Since this path is the longest path from $ u $ to $ v $, there would not be any incoming edge on $ u $ from any other vertex $ u ' $ (if that had been the case, then our longest path would have started from $ u ' $ itself or any other vertex but not $ u $ for sure) and similarly there will not be any outgoing edge from $ v $ to any vertex $ v ' $ (if that had been the case, then our longest path should not have ended at $ v $ but at $ v ' $ or some other vertex, but definitely not $ v $). So this proves that $ u $ has indegree $ 0 $ and $ v $ has outdegree $ 0 $ and this proof includes your answer.