Let G $=($V$,$E$)$ be a DAG. Prove that there exists a node v in V such that indeg$($v$)=0.$ Hint: Proceed

by contradiction. If $$v in V : indeg$($v$)>0,$ then pick some arbitrary node, v$.$ By assumption, there must

be an edge $($u$,$ v$)$ in E$.$ Follow the edge in reverse, i$.$e$.$ from v to u$.$ Repeat this process and derive a

contradiction by applying the pigeon hole principle.