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

Question

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.

Answer 1

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. So we can keep doing this procedure until we arrive at a node we already visited. That's because you can repeat this procedure infinite times but you only have a finite number of nodes. 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.

Answer 2

Just reverse the direction of all edges. This cannot produce a cycle where there wasn't one before, and the indegrees are now outdegrees.

Answer 3

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 the absence of cycles. Let's consider, WLOG, the longest path $ P $ in the graph, which is from vertex $ u $ to vertex $ v $. Since this path is the longest path, there would not be any incoming edge on $ u $ from some other vertex $ u ' $, in which case our longest path would have started from $ u ' $ instead of $ u $. And similarly there will not be any outgoing edge from $ v $ to some other vertex $ v ' $, in which case our longest path should have ended at $ v ' $ instead of $ v $. So this proves that $ u $ has an indegree $ 0 $ and $ v $ has an outdegree $ 0 $. And this proof includes your answer.

Answer 4

• 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.