Is it true that a directed graph with a finite number of ver

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

Solution

Yes it is true that a directed graph with finite number of vertices and with no directed cycles has at least one vertex whose outdegree is zero.

As know there is one directed edge between two vertices and there is one vertex that the out-degree is zero. If we want to fix that we can add a vertex and directed edge between new and old vertex that have out-degree zero. Again if you add new vertex you will find out-degree zero.

If we cconnect the vertex with out-degree zero to an existing vertex then we create directed circle.

Please see below diagram, consider vertex 1, 2 and 3 in below diagram

    Directed graph

     In – degree

    Out – degree

    in : 1 , out : 1

    in : 1,   out : 2

    in: 1 ,   out : 0