If G is a DAG we denote by τ (G) the number of distinct topological sorts of G. Now let G = (V, E) be any DAG. An add-one-vertex operation on G constructs a digraph G 0 = (V 0 , E 0 ) such that • G 0 is also a DAG. • We add exactly one new vertex, call it z that is, V 0 = V ∪ {z}, z ∈ / V . • We add some (possibly 0) new directed edges, that is, E 0 ⊇ E. (a) Prove that for any DAG G = (V, E) there is a way to perform an add-one-vertex operation on G such that the resulting DAG G 0 has the same number of topological sorts, i. e. τ (G 0 ) = τ (G). (b) Prove that for any DAG G there is a way to perform an add-one-