23.2.7. Existence of Vertex with Indegree 0

So, our first claim is that every DAG has at least one vertex with in degree 0, in terms of our example a vertex with in degree 0 is something which has no dependencies, nothing pointing into it.

The indegree of a vertex in a directed graph refers to the number of edges that point towards that vertex. A vertex with an indegree of 0 is one that has no incoming edges, meaning that it does not depend on any other vertex to be completed. In the context of Directed Acyclic Graphs (DAGs), this concept is crucial because it indicates starting points for processing the tasks represented by the vertices.

Consider a project where you need to complete various tasks like drafting a document, getting feedback, and submitting it. If drafting the document is the first step, it has no dependencies, thus representing a task with indegree 0. You must have that completed before you can get feedback or submit the document.

Now, how do we prove this? Supposing we start with any vertex v such that has in degree greater than 0... So, in any directed acyclic graph, there must be at least one vertex with in degree 0, which corresponds to a task with no dependencies from where we can start or a numeration of the tasks.

To establish that there is at least one vertex with indegree 0, we assume the contrary: that all vertices have indegree greater than 0. Following this assumption, each vertex must point to another vertex, leading to a chain of dependencies. Eventually, this creates a cyclic dependency where a vertex depends on another in a loop. This contradicts the definition of a DAG, which is acyclic by nature. Hence, there must be at least one vertex with indegree 0, where you can commence.

Imagine a line of dominoes set up in a circle. If each domino can only fall if another before it falls (representing dependencies), you can't start the sequence because you’ll always go back to the first one. Now, if even one domino were standing alone, unconnected to the rest, you could knock it down first. This represents our vertex with indegree 0.

So, this is a more elaborate version of the algorithm that it described earlier. So, we pick a vertex with indegree 0, we call that a vertex that has no dependencies... each n vertex to enumerate we will delete from the DAG.

The process of enumerating vertices with indegree 0 is essentially an iterative approach to scheduling tasks. Once a vertex with indegree 0 is identified, it can be completed, at which point it is removed from the graph. This action will affect the indegrees of other vertices, potentially revealing new vertices with indegree 0. This continues until all vertices are processed, effectively yielding a topological sort of the tasks.

Think of a cooking process where one dish must be prepared before another can be made. You might start with a dish that has no prerequisites (indegree 0). Once that's cooked, you finish it and move on to the next dish that may have once depended on it. This stepwise removal of completed tasks allows you to systematically finish your meal.

--