Having No Directed Cycles Guarantees a Vertex of Zero Outdegree

Question

Is it true that a directed graph with a finite number of vertices and with no directed cycles has at least one vertex whose out-degree is zero?

Here is my idea:

Suppose there is no vertex with out-degree zero, this implies there is an outgoing edge from each vertex. Suppose there are $n$ vertices then there must be $n$ edges since out-degree is greater than or equal to 1, but we can't have this since it creates a directed cycle. Hence, there must be a vertex whose out-degree is zero.

Is this correct? Can you provide a mathematical proof or counterexample?

Answer 1

You basically have the right idea, but I would organize it as a contraposition.

Statement: Let $G$ be a directed graph with a finite number of vertices. If $G$ has no directed cycles, then it has at least one vertex with outdegree zero.

Contrapositive: Let $G$ be a directed graph with a finite number of vertices. If $G$ has no vertex with outdegree zero, then it has a directed cycle.

Proof (sketch): Start at any vertex. Since it's outdegree is not zero, you can travel along an edge. Your new position is also a vertex with nonzero outdegree, so you can travel along an edge. Keep travelling in this way (it's always possible, since every vertex has nonzero outdegree). Since $G$ is finite, you must eventually return to a vertex you've previously visited, which indicates the presence of a directed cycle.

Answer 2

Take the longest directed path in $G$. The end vertex of the path has the desired property.