DAG topological sort proof Prove that for any DAG we can add one new vertex to the DAG (and still keep it DAG) that will have the same number of topological sorts. I'm finding it difficult to understand why is it correct, so obviously it's difficult for me to prove it.

It depends on whether you can add edges, too.

Suppose a DAG $G$ has $k$ unique topological orders of $n$ vertices. Let $v$ denote a new vertex added to $G$. If there are no directed edges to $v$, then $v$ can occur anywhere in a topological order. So for each of the $k$ known topological orders that do not include $v$, there are now $n+1$ topological orders that include $v$ (where $v$ can come before/after any of the other $n$ vertices). So the new graph $G+\\{v\\}$ has $k(n+1)$ orders.

But, if you restrict that when you add $v$, you also add $n$ edges from each of the vertices of $G$ to $v$, then $v$ **must** be the last vertex of any topological order. So each of $k$ orders known for $G$ can be amended to include $v$ at the end and still be a valid topological order for the new graph. In this case, the new graph $G + \\{v\\}$ still has $k$ orders.