# Given a directed acyclic graph (DAG) - what can you say about each case?

Suppose $$G$$ is a DAG with $$n$$ vertices, and $$v$$ is a vertex of $$G$$. What can we say regarding $$v$$ if the following holds:

A. In all topological sorts, $$v$$ is at the end of the list.

So my initial answer is that $$v$$ is the "sink" vertex, but in some case its not always correct, can't seem to find a feature that cant be said on $$v$$?

B. In all topological sorts, $$v$$ is at the top of the list.

So this one is the opposite which is the source vertex and has arrows coming out of him and no one points to him.

• 'the "sink" vertex' -- this phrasing implies a DAG has exactly 1 sink vertex. – j_random_hacker May 2 '19 at 15:44
• Is topological cue the result of topological sorting on a DAG? Is your graph a DAG? – George Vidalakis May 2 '19 at 15:45
• @GeorgeVidalakis yes and yes – G95 May 2 '19 at 15:46
• @j_random_hacker topoligical sorting can bring diffrent results, what can I say for on v of question A? – G95 May 2 '19 at 15:49
• @GeorgeVidalakis: A sink is just a vertex with no out-edge. Your example DAG has two sinks. – j_random_hacker May 2 '19 at 16:23

A. Let's prove that $$v$$ will be a vertex which can be reached by every node (it is the mother vertex of the transpose of the graph) by contradiction. Suppose that there is a node $$u$$ such that $$v$$ is unreachable by it. Consider every node in the DAG reachable by $$u$$. There must be at least one node in this set that has no leaving edges. (Otherwise you could start from $$u$$ and always follow a leaving edge from the current node so after at most $$|V| - 1$$ steps you would visit an already visited node. But this implies a cycle which isn't allowd in a DAG.) So no other node is reachable by $$u$$ and $$u$$ could be last in a topological cue instead of $$v$$ and we reached a contradiction. As a result $$v$$ is reachable by every node. This is equivalent with (A)'s statement as a node being reachable by every node can appear only last in any topological cue.
Also $$v$$ is a sink because if it wasn't there would be at least one edge leaving it so it couldn't be at the end of any topological cue. (A)'s statement implies that $$v$$ is a sink but the reverse doesn't always hold.
B. $$v$$ is a mother vertex (every node is reachable by it). The proof is similar.