CODEWITHSUNDEEP
algorithmgraph-theorydirected-acyclic-graphstopological-sort
Manu
Manu

Reputation: 337

How can we prove there will be at least a vertex with in-degree of zero in Directed Acyclic graph?

I can see the hypothesis true intuitively but, mathematically I am not able to prove. Any help would be appreciated.

Upvotes: 1

Views: 1272

Answers (2)

Zahid Sikdar
Zahid Sikdar

Reputation: 21

Let us prove it mathematically.

Consider the directed graph G = (V, E), where V denotes the collection of vertices and E represents the set of edges.

Assume, for the sake of contradiction, that there is a DAG G with no vertex of degree zero.

Let v represent any vertex in G. There are no vertices with in-degree zero, hence every vertex must have at least one incoming edge.

Let u be a vertex for which a directed edge (u, v) exists. Given that v has an incoming edge, we can conclude that u must exist. However, since u is the origin of the edge (u, v), it also needs to have an incoming edge.

Following this logic, there must be another vertex u with an incoming edge (u, v) for each vertex v.

There is a limit to the number of vertices in the graph, therefore this procedure cannot go on forever. As a result, we have to finally arrive at a vertex that has no incoming edges.

Our hypothesis that there must be a DAG with no vertex of in-degree zero must be incorrect in light of this contradiction. There must be at least one vertex with in-degree zero in every DAG as a result.

Upvotes: 0

Peter de Rivaz
Peter de Rivaz

Reputation: 33519

Let this graph have n vertices.

Suppose we reverse all the edges, then we are trying to prove there is a vertex with an out-degree of zero.

If not, then simply start anywhere and travel along n edges (always possible as every vertex as non-zero out-degree). Therefore we have visited n+1 vertices - so at least 2 of them must be the same (pigeon hole principle), and therefore we have found a cycle in your acyclic graph.

Upvotes: 4

Related Questions