Reputation: 337
I can see the hypothesis true intuitively but, mathematically I am not able to prove. Any help would be appreciated.
Upvotes: 1
Views: 1269
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
Reputation: 33509
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