2
$\begingroup$

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?

$\endgroup$
0

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ thanks for the detailed proof $\endgroup$ Commented Nov 26, 2018 at 3:07
2
$\begingroup$

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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .