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.
 A: 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.
A: Just reverse the direction of all edges. This cannot produce a cycle where there wasn't one before, and the indegrees are now outdegrees.
A: 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.
A: *

*For undirected graphs:

Since all vertices are having an indegree $>1$, the count of all the indegrees on all the n different vertices will be  $\ge n$. However, if a graph (connected or not) has its number of vertices $> (n-1)$, then it will have at least one cycle. Hence Proved.

*

*For directed graphs: (existential proof)

Performing a search like DFS on a graph with all its vertices indegree $>0$ will guarantee to visit at least one vertex again (via. its indegree-edge and outdegree-edge) and thus forming a cycle.
