# Having No Directed Cycles Guarantees a Vertex of Zero Outdegree

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?

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.

• thanks for the detailed proof Commented Nov 26, 2018 at 3:07

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

• How do you know there is a longest directed path? Commented Nov 26, 2018 at 2:43
• It is a finite graph.
– hbm
Commented Nov 26, 2018 at 5:15